﻿#pragma once

#include "utility.h"

using namespace std;

class Solution
{
public:
	int minOperations(vector<int>& nums, int k) {
		// 配列 nums の要素合計を計算する
		long long sum = accumulate(nums.begin(), nums.end(), 0LL);
		// 合計を k で割った余りを求める
		int r = sum % k;
		// 余り r 回だけ要素を 1 減らす操作を行えば
		// 合計が k の倍数になる
		return r;
	}

	string reorderSpaces(string text) {
		// Count total spaces and split words
		int spaceCount = 0;
		vector<string> words;
		string currentWord;
		
		for (char c : text) {
			if (c == ' ') {
				spaceCount++;
				if (!currentWord.empty()) {
					words.push_back(currentWord);
					currentWord.clear();
				}
			} else {
				currentWord += c;
			}
		}
		if (!currentWord.empty()) {
			words.push_back(currentWord);
		}
		
		// Calculate spaces between words and remaining spaces
		int wordCount = words.size();
		int spacesBetween = wordCount > 1 ? spaceCount / (wordCount - 1) : 0;
		int remainingSpaces = wordCount > 1 ? spaceCount % (wordCount - 1) : spaceCount;
		
		// Build result string
		string result;
		for (int i = 0; i < words.size(); i++) {
			result += words[i];
			if (i < words.size() - 1) {
				result += string(spacesBetween, ' ');
			}
		}
		result += string(remainingSpaces, ' ');
		
		return result;
	}

	int passThePillow(int n, int time) {
		int pos = 1;      // 当前持枕头的位置
		int dir = 1;      // 方向：+1 表示向队尾传，-1 表示向队首传
		while (time--) {
			// 如果到达尽头，就换方向
			if (pos == n)      dir = -1;
			else if (pos == 1) dir = 1;
			// 按当前方向传递
			pos += dir;
		}
		return pos;
	}

	vector<int> distinctDifferenceArray(vector<int>& nums) {
		int n = nums.size();
		vector<int> diff(n, 0);

		// 计算前缀不同元素个数
		unordered_set<int> prefixSet;
		vector<int> prefixCount(n);
		for (int i = 0; i < n; i++) {
			prefixSet.insert(nums[i]);
			prefixCount[i] = prefixSet.size();
		}

		// 计算后缀不同元素个数
		unordered_set<int> suffixSet;
		vector<int> suffixCount(n, 0);
		for (int i = n - 1; i > 0; i--) {
			suffixSet.insert(nums[i]);
			suffixCount[i - 1] = suffixSet.size();
		}

		// 计算 diff 数组
		for (int i = 0; i < n; i++) {
			diff[i] = prefixCount[i] - suffixCount[i];
		}

		return diff;
	}
	
	int subarraySum(vector<int>& nums) {
		int n = nums.size();
		vector<int> prefixSum(n + 1, 0); // 前缀和数组，prefixSum[i] 表示 nums[0...i-1] 的和
		
		// 计算前缀和
		for (int i = 1; i <= n; ++i) {
			prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
		}

		int totalSum = 0;
		for (int i = 0; i < n; ++i) {
			int start = max(0, i - nums[i]);
			// 子数组 nums[start...i] 的和可以通过前缀和计算
			totalSum += prefixSum[i + 1] - prefixSum[start];
		}

		return totalSum;
    }

	vector<string> splitWordsBySeparator(vector<string>& words, char separator) {
        vector<string> result;
		for (const string& word : words) {
			stringstream ss(word); // 创建一个字符串流
			string segment;
			// 使用 getline 按分隔符拆分
			while (getline(ss, segment, separator)) {
				if (!segment.empty())
					result.push_back(segment);
			}
		}
		return result;
    }

	int generateKey(int num1, int num2, int num3) {
		int result = 0;
		int place = 1; // 位权，从个位开始
		for (int i = 0; i < 4; ++i) {
			int digit1 = num1 % 10; // 提取 num1 的最低位
			int digit2 = num2 % 10; // 提取 num2 的最低位
			int digit3 = num3 % 10; // 提取 num3 的最低位

			int minDigit = std::min({ digit1, digit2, digit3 }); // 当前位的最小值

			result += minDigit * place; // 将最小值加入结果
			place *= 10; // 更新位权

			num1 /= 10; // 去掉最低位
			num2 /= 10;
			num3 /= 10;
		}
		return result;
	}

	int semiOrderedPermutation(std::vector<int>& nums) {
		int n = nums.size();
		int pos1 = 0, posN = 0;

		// 找到 1 和 n 的初始位置
		for (int i = 0; i < n; ++i) {
			if (nums[i] == 1) pos1 = i;
			if (nums[i] == n) posN = i;
		}

		// 计算最小操作次数
		if (pos1 < posN) {
			return pos1 + (n - 1 - posN);
		}
		else {
			return pos1 + (n - 1 - posN) - 1;
		}
	}

	int minOperations(std::vector<int>& nums, int k) {
		std::unordered_set<int> collected;
		int operations = 0;
		// 从数组末尾开始遍历
		for (int i = nums.size() - 1; i >= 0; --i) {
			if (nums[i] <= k) {
				collected.insert(nums[i]); // 收集数字
			}
			operations++;
			if (collected.size() == k) {
				return operations; // 当收集到 1 到 k 时，返回操作次数
			}
		}
		return -1; // 理论上不可能到这里，因为输入保证可以收集到 1 到 k
	}

	int minChanges(int n, int k) {
		// 如果 k 有的位是 1，而 n 没有，那就是无法实现
		if ((n | k) != n)
			return -1;
		int changes = 0;
		while (n > 0) {
			if ((n & 1) && !(k & 1))
				changes++; // n 的当前位是 1，而 k 的当前位是 0，需要更改
			n >>= 1;
			k >>= 1;
		}
		return changes;
	}

	std::string convertDateToBinary(std::string date) {
		std::string year = date.substr(0, 4);
		std::string month = date.substr(5, 2);
		std::string day = date.substr(8, 2);
		int yearInt = std::stoi(year);
		int monthInt = std::stoi(month);
		int dayInt = std::stoi(day);
		std::string yearBinary = std::bitset<16>(yearInt).to_string();
		std::string monthBinary = std::bitset<8>(monthInt).to_string();
		std::string dayBinary = std::bitset<8>(dayInt).to_string();
		yearBinary = yearBinary.substr(yearBinary.find('1'));
		monthBinary = monthBinary.substr(monthBinary.find('1'));
		dayBinary = dayBinary.substr(dayBinary.find('1'));
		return yearBinary + "-" + monthBinary + "-" + dayBinary;
	}

	bool isFascinating(int n) {
		string concatenated = to_string(n) + to_string(n * 2) + to_string(n * 3);
		if (concatenated.length() != 9)
			return false;
		bool digits[10] = { false };
		for (char c : concatenated) {
			int digit = c - '0';
			if (digit == 0 || digits[digit])
				return false;
			digits[digit] = true;
		}
		return true;
	}

	bool isSumEqual(string firstWord, string secondWord, string targetWord) {
		auto wordToValue = [](const std::string& word) -> int {
			std::string numStr;
			for (char c : word)
				numStr += std::to_string(c - 'a');  // 将字符转换为字母表中的数值
			return std::stoi(numStr);  // 转换为整数
		};
		return wordToValue(firstWord) + wordToValue(secondWord) == wordToValue(targetWord);
	}

	vector<int> resultArray(vector<int>& nums) {
		vector<int> arr1{ nums[0] }, arr2{ nums[1] };
		for (size_t i = 2; i < nums.size(); i++)
		{
			if (*arr1.rbegin() > *arr2.rbegin())
				arr1.emplace_back(nums[i]);
			else
				arr2.emplace_back(nums[i]);
		}
		arr1.insert(arr1.end(), arr2.begin(), arr2.end());
		return arr1;
	}

	int sumOfSquares(vector<int>& nums) {
		int res{};
		int n = nums.size();
		for (size_t i = 0; i < n; i++)
		{
			if (n % (i + 1) == 0)
				res += nums[i] * nums[i];
		}
		return res;
	}

	vector<int> getSneakyNumbers(vector<int>& nums) {
		vector<int> res;
		unordered_map<int, int> map;
		for (size_t i = 0; i < nums.size(); i++)
		{
			if (map[nums[i]] == 1)
				res.emplace_back(nums[i]);
			else
				++map[nums[i]];
		}
		return res;
	}

	vector<int> stableMountains(vector<int>& height, int threshold) {
		vector<int> res;
		for (size_t i = 1; i < height.size(); i++)
		{
			if (height[i - 1] > threshold)
				res.emplace_back(i);
		}
		return res;
	}

	string clearDigits(string s) {
		stack<char> ss;
		for (char c : s) {
			if (!isdigit(c))
				ss.push(c);
			else if (!ss.empty())
				ss.pop();
		}
		string res;
		while (!ss.empty()) {
			res.push_back(ss.top());
			ss.pop();
		}
		std::reverse(res.begin(), res.end());
		return res;
	}

	bool canAliceWin(vector<int>& nums) {
		int sum1 = 0, sum2 = 0;
		for (size_t i = 0; i < nums.size(); i++)
		{
			if (nums[i] < 10)
				sum1 += nums[i];
			else
				sum2 += nums[i];
		}
		return sum1 != sum2;
	}

	int finalPositionOfSnake(int n, vector<string>& commands) {
		int res{};
		for (const string& command : commands)
		{
			if (command == "UP")
				res -= n;
			else if (command == "DOWN")
				res += n;
			else if (command == "LEFT")
				res -= 1;
			else if (command == "RIGHT")
				res += 1;
		}
		return res;
	}

	bool areOccurrencesEqual(string s) {
		int hashTable[26] = {};
		for (char c : s)
			++hashTable[c - 'a'];
		int n{};
		for (int i = 0; i < 26; i++) {
			if (hashTable[i] != 0) {
				if (n == 0)
					n = hashTable[i];
				else
					if (hashTable[i] != n)
						return false;
			}
		}
		return true;
	}

	int sumOfEncryptedInt(vector<int>& nums) {
		auto encrypt = [](int x) {
			// 将整数转为字符串以便处理每一个数位
			std::string str_x = std::to_string(x);
			// 找到最大的数位
			char max_digit = *std::max_element(str_x.begin(), str_x.end());
			// 用最大的数位替换所有数位
			std::string encrypted_str(str_x.size(), max_digit);
			// 将加密后的字符串转为整数
			return std::stoi(encrypted_str);
		};

		int total_sum = 0;
		for (int num : nums)
			total_sum += encrypt(num);
		return total_sum;
	}

	vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
		int n = grid.size();
		vector<int> count(n * n + 1);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				count[grid[i][j]]++;
			}
		}

		vector<int> res(2);
		for (int i = 1; i <= n * n; i++) {
			if (count[i] == 2) {
				res[0] = i;
			}
			if (count[i] == 0) {
				res[1] = i;
			}
		}
		return res;
	}

	bool isArraySpecial(vector<int>& nums) {
		for (int i = 1; i < nums.size(); i++) {
			if ((nums[i - 1] + nums[i]) % 2 == 0)
				return false;
		}
		return true;
	}

	int findChampion(vector<vector<int>>& grid) {
		int n = grid.size();
		for (int i = 0; i < n; i++) {
			if (accumulate(grid[i].begin(), grid[i].end(), 0) == n - 1) {
				return i;
			}
		}
		return -1;
	}

	int maximumDifference(vector<int>& nums) {
		int n = nums.size();
		int ans = -1, premin = nums[0];
		for (int i = 1; i < n; ++i) {
			if (nums[i] > premin) {
				ans = max(ans, nums[i] - premin);
			}
			else {
				premin = nums[i];
			}
		}
		return ans;
	}

	vector<int> findPeaks(vector<int>& mountain) {
		vector<int> res;
		for (int i = 1; i < mountain.size() - 1; i++) {
			if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1])
				res.emplace_back(i);
		}
		return res;
	}

	int findPermutationDifference(string s, string t) {
		int res{};
		int hashTable[26] = { 0 };
		for (int i = 0; i < s.length(); i++)
			hashTable[s[i] - 'a'] = i;
		for (int i = 0; i < t.length(); i++)
			res += std::abs(hashTable[t[i] - 'a'] - i);
		return res;
	}

	int minimumChairs(string s) {
		int num{};
		int res{};
		for (char c : s)
		{
			if (c == 'E')
				++num;
			else
				--num;
			res = std::max(num, res);
		}
		return res;
	}

	int minimumOperations(vector<int>& nums) {
		int op{};
		for (int num : nums)
		{
			int n = num % 3;
			op += std::min(n, 3 - n);
		}
		return op;
	}

	double minimumAverage(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		double res{ 50 };
		int size = nums.size();
		for (int i = 0; i < size / 2; i++)
			res = std::min((nums[i] + nums[size - 1 - i]) / 2.0, res);
		return res;
	}

	int distributeCandies1(vector<int>& candyType) {
		unordered_set<int> temp;
		for (int e : candyType)
			temp.insert(e);
		return std::min(candyType.size() / 2, temp.size());
	}

	int distributeCandies(int n, int limit) {
		int count{};
		for (int i = 0; i <= std::min(n, limit); i++) {
			for (int j = 0; j <= std::min(n - i, limit); j++) {
				if (n - i - j <= limit)
					++count;
			}
		}
		return count;
	}

	int countKeyChanges(string s) {
		int count{};
		for (int i = 1; i < s.length(); i++) {
			if (s[i] != s[i - 1] && std::abs(s[i] - s[i - 1]) != 32)
				++count;
		}
		return count;
	}

	int sumOfTheDigitsOfHarshadNumber(int x) {
		int sum{ ::digitSum(x) };
		return x % sum == 0 ? sum : -1;
	}

	int returnToBoundaryCount(vector<int>& nums) {
		int res{};
		int sum{};
		for (int num : nums)
		{
			sum += num;
			if (sum == 0)
				++res;
		}
		return res;
	}

	int addedInteger(vector<int>& nums1, vector<int>& nums2) {
		return *min_element(nums2.begin(), nums2.end()) - *min_element(nums1.begin(), nums1.end());
	}

	/*int minOperations(vector<int>& nums, int k) {
		sort(nums.begin(), nums.end());
		return std::distance(nums.begin(), std::lower_bound(nums.begin(), nums.end(), k));
	}*/

	int scoreOfString(string s) {
		int score{};
		for (int i = 0; i < s.length() - 1; i++)
			score += std::abs(s[i + 1] - s[i]);
		return score;
	}

	ListNode* deleteDuplicates(ListNode* head) {
		ListNode* result{ head };
		ListNode* last{ nullptr };
		while (head) {
			if (last && last->val == head->val)
				last->next = head->next;
			else
				last = head;
			head = head->next;
		}
		return result;
	}

	string longestCommonPrefix(vector<string>& strs) {
		string res;
		for (int i = 0; i <= 200; i++) {
			char c = ' ';
			for (string str : strs) {
				if (i >= str.length())
					return res;
				if (c != ' ' && c != str[i])
					return res;
				c = str[i];
			}
			res.push_back(c);
		}
		return res;
	}

	int countWords(vector<string>& words1, vector<string>& words2) {
		unordered_map<string, bool> ht1, ht2;
		auto&& func = [](const vector<string>& words, unordered_map<string, bool>& ht) {
			for (const string& word : words) {
				auto it = ht.find(word);
				if (it != ht.end()) it->second = false;
				else ht.insert({ word, true });
			}
		};
		func(words1, ht1);
		func(words2, ht2);
		int count{};
		for (auto p : ht1) {
			if (!p.second)
				continue;
			auto it = ht2.find(p.first);
			if (it != ht2.end() && it->second)
				++count;
		}
		return count;
	}

	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		std::vector<int> dst;
		std::merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), std::back_inserter(dst));
		int n = dst.size();
		return (n & 1) == 0 ? (dst[(n - 1) >> 1] + dst[n >> 1]) / 2.0 : dst[n >> 1];
	}

	int minLength(string s) {
		stack<char> tmp;
		for (char c : s) {
			if (!tmp.empty()) {
				if ((c == 'B' && tmp.top() == 'A') || (c == 'D' && tmp.top() == 'C')) {
					tmp.pop(); continue;
				}
			}
			tmp.push(c);
		}
		return tmp.size();
	}

	vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
		sort(potions.begin(), potions.end());
		vector<int> res;
		for (auto& i : spells) {
			long long t = (success + i - 1) / i - 1;
			res.push_back(potions.size() - (upper_bound(potions.begin(), potions.end(), t) - potions.begin()));
		}
		return res;
	}

	int triangleNumber(vector<int>& nums) {
		int n = nums.size();
		sort(nums.begin(), nums.end());
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				int left = j + 1, right = n - 1, k = j;
				while (left <= right) {
					int mid = (left + right) / 2;
					if (nums[mid] < nums[i] + nums[j]) {
						k = mid;
						left = mid + 1;
					}
					else {
						right = mid - 1;
					}
				}
				ans += k - j;
			}
		}
		return ans;
	}

	vector<int> findClosestElements(vector<int>& arr, int k, int x) {
		sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
			return abs(a - x) < abs(b - x) || abs(a - x) == abs(b - x) && a < b;
			});
		sort(arr.begin(), arr.begin() + k);
		return vector<int>(arr.begin(), arr.begin() + k);
	}

	int singleNonDuplicate(vector<int>& nums) {
		//
	}

	int hIndex(vector<int>& citations) {
		sort(citations.begin(), citations.end());
		int h = 0, i = citations.size() - 1;
		while (i >= 0 && citations[i] > h) {
			h++;
			i--;
		}
		return h;
	}

	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		int m = matrix.size(), n = matrix[0].size();
		int left = 0, right = m - 1;
		while (left <= right)
		{
			int middle = left + (right - left) / 2;
			if (matrix[middle][n - 1] < target)
				left = middle + 1;
			else if (matrix[middle][0] > target)
				right = middle - 1;
			else
				return binary_search(matrix[middle].begin(), matrix[middle].end(), target);
		}
		return false;
	}

	int findMin(vector<int>& nums) {
		int low = 0;
		int high = nums.size() - 1;
		while (low < high) {
			int pivot = low + (high - low) / 2;
			if (nums[pivot] < nums[high]) {
				high = pivot;
			}
			else {
				low = pivot + 1;
			}
		}
		return nums[low];
	}

	ListNode* removeNodes(ListNode* head) {
		stack<ListNode*> st;
		for (; head != nullptr; head = head->next) {
			st.push(head);
		}
		for (; !st.empty(); st.pop()) {
			if (head == nullptr || st.top()->val >= head->val) {
				st.top()->next = head;
				head = st.top();
			}
		}
		return head;
	}

	vector<int> findRightInterval(vector<vector<int>>& intervals) {
		vector<pair<int, int>> startIntervals;
		int n = intervals.size();
		for (int i = 0; i < n; i++) {
			startIntervals.emplace_back(intervals[i][0], i);
		}
		sort(startIntervals.begin(), startIntervals.end());

		vector<int> ans(n, -1);
		for (int i = 0; i < n; i++) {
			auto it = lower_bound(startIntervals.begin(), startIntervals.end(), make_pair(intervals[i][1], 0));
			if (it != startIntervals.end()) {
				ans[i] = it->second;
			}
		}
		return ans;
	}

	int countNegatives(vector<vector<int>>& grid) {
		int count{};
		int m = grid.size(), n = grid[0].size();
		int index = 0;
		for (int i = 0; i < m; i++) {
			auto&& end = grid[i].rend();
			auto&& it = lower_bound(grid[i].rbegin() + index, end, 0);
			index = n - std::distance(it, end);
			count += it == end ? n : index;
		}
		return count;
	}

	string shortestCompletingWord(string licensePlate, vector<string>& words) {
		array<int, 26> cnt{};
		for (char ch : licensePlate) {
			if (isalpha(ch)) {
				++cnt[tolower(ch) - 'a'];
			}
		}
		int idx = -1;
		for (int i = 0; i < words.size(); ++i) {
			array<int, 26> c{};
			for (char ch : words[i])
				++c[ch - 'a'];
			bool ok = true;
			for (int j = 0; j < 26; ++j) {
				if (c[j] < cnt[j]) {
					ok = false; break;
				}
			}
			if (ok && (idx < 0 || words[i].length() < words[idx].length()))
				idx = i;
		}
		return words[idx];
	}

	bool isAlienSorted(vector<string>& words, string order) {
		int hashTable[26]{ 0 };
		for (int i = 0; i < order.length(); i++)
			hashTable[order[i] - 'a'] = i + 1;

		auto&& greater = [&hashTable](string s1, string s2) {
			for (int i = 0; i < std::max(s1.length(), s2.length()); i++) {
				int a = i < s1.length() ? hashTable[s1[i] - 'a'] : 0;
				int b = i < s2.length() ? hashTable[s2[i] - 'a'] : 0;
				if (a == b) continue;
				return a > b;
			}
			return false;
		};

		for (int i = 0; i < words.size() - 1; i++) {
			if (greater(words[i], words[i + 1]))
				return false;
		}
		return true;
	}

	vector<int> constructRectangle(int area) {
		for (int i = ceil(sqrt(area)); i <= area; i++) {
			if (area % i == 0)
				return { i, area / i };
		}
		return { area, 1 };
	}

	// 计算最大三角形的面积
	double largestTriangleArea(vector<vector<int>>& points) {
		double maxArea = 0;
		int n = points.size();
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					double area = triangleArea(points[i], points[j], points[k]);
					maxArea = max(maxArea, area);
				}
			}
		}
		return maxArea;
	}

	bool isIsomorphic(string s, string t) {
		unordered_map<char, char> s2t;
		unordered_map<char, char> t2s;
		for (int i = 0; i < s.length(); ++i) {
			char x = s[i], y = t[i];
			if ((s2t.count(x) && s2t[x] != y) || (t2s.count(y) && t2s[y] != x)) {
				return false;
			}
			s2t[x] = y;
			t2s[y] = x;
		}
		return true;
	}

	int subsetXORSum(vector<int>& nums) {
		int res = 0;
		int n = nums.size();
		for (int i = 0; i < (1 << n); ++i) {   // 遍历所有子集
			int tmp = 0;
			for (int j = 0; j < n; ++j) {   // 遍历每个元素
				if (i & (1 << j)) {
					tmp ^= nums[j];
				}
			}
			res += tmp;
		}
		return res;
	}

	bool isRobotBounded(string instructions) {
		vector<vector<int>> direc{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
		int direcIndex = 0;
		int x = 0, y = 0;
		for (char instruction : instructions) {
			if (instruction == 'G') {
				x += direc[direcIndex][0];
				y += direc[direcIndex][1];
			}
			else if (instruction == 'L') {
				direcIndex += 3;
				direcIndex %= 4;
			}
			else {
				direcIndex++;
				direcIndex %= 4;
			}
		}
		return direcIndex != 0 || (x == 0 && y == 0);
	}

	vector<int> spiralOrder(vector<vector<int>>& matrix) {
		vector<int> result;
		if (matrix.empty())
			return result;
		int m = matrix.size(), n = matrix[0].size();
		int top = 0, bottom = m - 1, left = 0, right = n - 1;
		while (top <= bottom && left <= right) {
			for (int i = left; i <= right; i++)
				result.emplace_back(matrix[top][i]);
			top++;
			for (int i = top; i <= bottom; i++)
				result.emplace_back(matrix[i][right]);
			right--;
			if (top <= bottom && left <= right) {
				for (int i = right; i >= left; i--)
					result.emplace_back(matrix[bottom][i]);
				bottom--;
				for (int i = bottom; i >= top; i--)
					result.emplace_back(matrix[i][left]);
				left++;
			}
		}
		return result;
	}

	string multiply(string num1, string num2) {
		int m = num1.size(), n = num2.size();
		string res(m + n, '0');
		for (int i = m - 1; i >= 0; i--) {
			int carry = 0;
			for (int j = n - 1; j >= 0; j--) {
				int temp = (res[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
				res[i + j + 1] = temp % 10 + '0';
				carry = temp / 10;
			}
			res[i] += carry;
		}
		size_t pos = res.find_first_not_of("0");
		if (string::npos != pos)
			return res.substr(pos);
		return "0";
	}

	double quickMul(double x, long long N) {
		if (N == 0) {
			return 1.0;
		}
		double y = quickMul(x, N / 2);
		return N % 2 == 0 ? y * y : y * y * x;
	}

	double myPow(double x, int n) {
		long long N = n;
		return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
	}

	vector<int> numberGame(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size(); i += 2) {
			swap(nums[i], nums[i + 1]);
		}
		return nums;
	}

	long long minCost(vector<int>& nums, int x) {
		int n = nums.size();
		vector<int> f(nums);
		long long ans = accumulate(f.begin(), f.end(), 0LL);
		for (int k = 1; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				f[i] = min(f[i], nums[(i + k) % n]);
			}
			ans = min(ans, static_cast<long long>(k) * x + accumulate(f.begin(), f.end(), 0LL));
		}
		return ans;
	}

	int countOdds(int low, int high) {
		const auto& pre = [](int x) {
			return (x + 1) >> 1;
		};
		return pre(high) - pre(low - 1);
	}

	string tictactoe(vector<vector<int>>& moves) {
		int tmp[3][3]{};
		for (int i = 1; auto & v : moves) {
			tmp[v[0]][v[1]] = i;
			i = -i;
		}
		if (abs(tmp[0][0] + tmp[1][1] + tmp[2][2]) == 3 || abs(tmp[0][2] + tmp[1][1] + tmp[2][0]) == 3)
			return tmp[1][1] > 0 ? "A" : "B";
		for (int i = 0; i < 3; ++i)
			if (abs(tmp[i][0] + tmp[i][1] + tmp[i][2]) == 3 || abs(tmp[0][i] + tmp[1][i] + tmp[2][i]) == 3)
				return tmp[i][i] > 0 ? "A" : "B";
		return moves.size() == 9 ? "Draw" : "Pending";
	}

	bool judgeCircle(string moves) {
		char hashTable[26] = { 0 };
		for (char c : moves)
			++hashTable[c - 'A'];
		return hashTable['U' - 'A'] == hashTable['D' - 'A'] && hashTable['L' - 'A'] == hashTable['R' - 'A'];
	}

	int calPoints(vector<string>& operations) {
		std::stack<int> s;
		for (const std::string& op : operations) {
			if (op == "+") {
				int value2 = s.top(); s.pop();
				int value1 = s.top();
				s.push(value2);
				s.push(value1 + value2);
			}
			else if (op == "D")
				s.push(s.top() * 2);
			else if (op == "C")
				s.pop();
			else
				s.push(std::stoi(op));
		}
		int result{};
		while (!s.empty()) {
			result += s.top(); s.pop();
		}
		return result;
	}

	string toLowerCase(string s) {
		for (int i = 0; i < s.length(); i++) {
			if (std::isupper(s[i]))
				s[i] = std::tolower(s[i]);
		}
		return s;
	}

	int lengthOfLastWord(string s) {
		int index = s.size() - 1;

		while (s[index] == ' ') {
			index--;
		}
		int wordLength = 0;
		while (index >= 0 && s[index] != ' ') {
			wordLength++;
			index--;
		}

		return wordLength;
	}

	int romanToInt(string s) {
		int res{};
		unordered_map<string, int> hashTable = { {"I", 1}, {"V", 5}, {"X", 10}, {"L", 50}, {"C", 100}, {"D", 500}, {"M", 1000},
			{"IV", 4}, {"IX", 9}, {"XL", 40}, {"XC", 90}, {"CD", 400}, {"CM", 900} };
		int len = s.length();
		for (int i = 0; i < len; i++) {
			if (i < len - 1 && (s[i] == 'I' || s[i] == 'X' || s[i] == 'C')) {
				auto it = hashTable.find(string{ s[i], s[i + 1] });
				if (it != hashTable.end()) {
					res += it->second; ++i; continue;
				}
			}
			auto it = hashTable.find(string{ s[i] });
			res += it->second;
		}
		return res;
	}

	bool isMonotonic(vector<int>& nums) {
		if (nums.size() < 3)
			return true;
		bool rise = true, decline = true;
		for (int i = 0; i < nums.size() - 1; ++i)
		{
			if (nums[i + 1] < nums[i])
				rise = false;
			else if (nums[i + 1] > nums[i])
				decline = false;
			if (!rise && !decline)
				break;
		}
		return rise || decline;
	}

	vector<int> plusOne(vector<int>& digits) {
		int carry{ 1 };
		for (int i = digits.size() - 1; i >= 0; i--) {
			digits[i] += carry;
			carry = digits[i] / 10;
			digits[i] %= 10;
		}
		if (carry != 0)
			digits.insert(digits.begin(), carry);
		return digits;
	}

	int isWinner(vector<int>& player1, vector<int>& player2) {
		int score1 = 0, score2 = 0;
		for (int i = 0; i < player1.size(); i++) {
			if (i >= 1) {
				if (player1[i - 1] == 10 || (i - 2 >= 0 && player1[i - 2] == 10))
					score1 += player1[i];
				if (player2[i - 1] == 10 || (i - 2 >= 0 && player2[i - 2] == 10))
					score2 += player2[i];
			}
			score1 += player1[i];
			score2 += player2[i];
		}
		return score1 > score2 ? 1 : (score1 < score2 ? 2 : 0);
	}

	void moveZeroes(vector<int>& nums) {
		int n = nums.size(), left = 0, right = 0;
		while (right < n) {
			if (nums[right]) {
				swap(nums[left], nums[right]);
				left++;
			}
			right++;
		}
	}

	bool repeatedSubstringPattern(string s) {
		int len = s.length();
		string sub = "";
		for (int i = 0; i < len / 2; i++) {
			sub += s[i];
			if (len % (i + 1) != 0)
				continue;
			string temp = "";
			for (int j = 0; j < len / (i + 1); j++) {
				temp += sub;
			}
			if (temp == s)
				return true;
		}
		return false;
	}

	char findTheDifference(string s, string t) {
		char hashTable[26] = { 0 };
		for (char c : s)
			++hashTable[c - 'a'];
		for (char c : t) {
			--hashTable[c - 'a'];
			if (hashTable[c - 'a'] < 0)
				return c;
		}
		return 'a';
	}

	string mergeAlternately(string word1, string word2) {
		int p1 = 0, p2 = 0;
		string s = "";
		while (p1 < word1.length() || p2 < word2.length()) {
			if (p1 < word1.length()) {
				s.push_back(word1[p1]);
				++p1;
			}
			if (p2 < word2.length()) {
				s.push_back(word2[p2]);
				++p2;
			}
		}
		return s;
	}

	string stringShift(string s, vector<vector<int>>& shift) {
		int len = s.length();
		for (auto&& op : shift) {
			op[1] %= len;
			if (op[0] != 0)
				op[1] = len - op[1];
			string left = string(s.begin(), s.begin() + op[1]);
			string right = string(s.begin() + op[1], s.end());
			s = right + left;
		}
		return s;
	}

	bool isConsecutive(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size() - 1; i++) {
			if (nums[i + 1] - nums[i] != 1)
				return false;
		}
		return true;
	}

	int sumOfDigits(vector<int>& nums) {
		int min = *min_element(nums.begin(), nums.end());
		int sum{};
		for (char c : to_string(min))
			sum += c - '0';
		return sum % 2 == 0 ? 1 : 0;
	}

	int countElements(vector<int>& arr) {
		int hashTable[1001] = { 0 };
		for (int n : arr) {
			++hashTable[n];
		}
		int count{};
		for (int i = 0; i < 1000; i++) {
			if (hashTable[i] > 0 && hashTable[i + 1] > 0)
				count += hashTable[i];
		}
		return count;
	}

	bool confusingNumber(int n) {
		string s = to_string(n);
		string res = "";
		for (char c : s) {
			if (c != '0' && c != '1' && c != '6' && c != '8' && c != '9')
				return false;
			if (c == '6') c = '9';
			else if (c == '9') c = '6';
			res.push_back(c);
		}
		reverse(res.begin(), res.end());
		return s != res;
	}

	vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
		int right{ tomatoSlices - 2 * cheeseSlices };
		for (int x = 0; x <= cheeseSlices; x++) {
			int left{ x << 1 };
			if (left > right)
				break;
			if (left == right)
				return { x, cheeseSlices - x };
		}
		return {};
	}

	int calculateTime(string keyboard, string word) {
		int hashTable[26] = { 0 };
		for (int i = 0; i < keyboard.length(); i++) {
			hashTable[keyboard[i] - 'a'] = i;
		}
		int time{ hashTable[word[0] - 'a'] };
		for (int i = 1; i < word.size(); i++) {
			time += std::abs(hashTable[word[i] - 'a'] - hashTable[word[i - 1] - 'a']);
		}
		return time;
	}

	string removeVowels(string s) {
		string ans = "";
		for (int i = 0; i < s.length(); i++) {
			if (s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u')
				ans.push_back(s[i]);
		}
		return ans;
	}

	int houseCount(Street* street, int k) {
		for (int i = 0; i < k; i++) {
			street->closeDoor();
			street->moveRight();
		}

		street->openDoor();
		street->moveRight();

		int ans = 1;
		while (!street->isDoorOpen()) {
			ans++;
			street->moveRight();
		}
		return ans;
	}

	int sumCounts(vector<int>& nums) {
		int sum{};
		int size{ (int)nums.size() };
		for (int i = 0; i < size; i++) {
			bool hashTable[100] = { false };
			int count{};
			for (int j = i; j < size; j++) {
				for (int k = i; k <= j; k++) {
					if (!hashTable[nums[k] - 1]) {
						hashTable[nums[k] - 1] = true;
						++count;
					}
				}
				sum += count * count;
			}
		}
		return sum;
	}

	int vowelStrings(vector<string>& words, int left, int right) {
		auto isVowel = [](char c) {
			return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
		};
		int count{};
		for (int i = left; i <= right; i++) {
			string word = words[i];
			if (isVowel(word[0]) && isVowel(*word.rbegin()))
				++count;
		}
		return count;
	}

	int runeReserve(vector<int>& runes) {
		sort(runes.begin(), runes.end());
		int ans = 1, cnt = 1;
		for (int i = 1; i < runes.size(); i++)
			if (runes[i] - runes[i - 1] > 1)
				cnt = 1;
			else
				ans = max(ans, ++cnt);
		return ans;
	}

	int findPeakElement(vector<int>& nums) {
		return max_element(nums.begin(), nums.end()) - nums.begin();
	}

	int countTestedDevices(vector<int>& batteryPercentages) {
		int count{};
		for (int i = 0; i < batteryPercentages.size(); i++) {
			if (batteryPercentages[i] - count > 0)
				++count;
		}
		return count;
	}

	string makeSmallestPalindrome(string s) {
		int len = s.length();
		for (int i = 0; i < len / 2; i++) {
			char first = s[i];
			char last = s[len - 1 - i];
			if (first > last)
				s[i] = last;
			else if (first < last)
				s[len - 1 - i] = first;
		}
		return s;
	}

	int dfs(int x, int parent, vector<vector<pair<int, int>>>& e) {
		int res = 0;
		for (auto& edge : e[x]) {
			if (edge.first == parent) {
				continue;
			}
			res += edge.second + dfs(edge.first, x, e);
		}
		return res;
	}

	int minReorder(int n, vector<vector<int>>& connections) {
		vector<vector<pair<int, int>>> e(n);
		for (auto edge : connections) {
			e[edge[0]].push_back(make_pair(edge[1], 1));
			e[edge[1]].push_back(make_pair(edge[0], 0));
		}
		return dfs(0, -1, e);
	}

	string largestGoodInteger(string num) {
		char largest{ '\n' };
		for (int i = 0; i < num.size() - 2; i++) {
			if (num[i] == num[i + 1] && num[i] == num[i + 2])
				largest = std::max(num[i], largest);
		}
		if (largest == '\n')
			return "";
		return string(3, largest);
	}

	string makeGood(string s) {
		stack<char> stack;
		for (char c : s) {
			if (!stack.empty() && abs(stack.top() - c) == 32)
				stack.pop();
			else
				stack.push(c);
		}
		return stackToString(stack);
	}

	string maximumTime(string time) {
		if (time[0] == '?') {
			time[0] = ('4' <= time[1] && time[1] <= '9') ? '1' : '2';
		}
		if (time[1] == '?') {
			time[1] = (time[0] == '2') ? '3' : '9';
		}
		if (time[3] == '?') {
			time[3] = '5';
		}
		if (time[4] == '?') {
			time[4] = '9';
		}
		return time;
	}

	string maximumOddBinaryNumber(string s) {
		sort(s.begin(), s.end(), std::greater());
		int len = s.length();
		for (int i = len - 2; i >= 0; i--) {
			if (s[i] == '1') {
				std::swap(s[i], s[len - 1]);
				break;
			}
		}
		return s;
	}

	int sum = 0;

	TreeNode* bstToGst(TreeNode* root) {
		if (root != nullptr) {
			bstToGst(root->right);
			sum += root->val;
			root->val = sum;
			bstToGst(root->left);
		}
		return root;
	}

	int maxScore(vector<int>& cardPoints, int k) {
		int n = cardPoints.size();
		// 滑动窗口大小为 n-k
		int windowSize = n - k;
		// 选前 n-k 个作为初始值
		int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);
		int minSum = sum;
		for (int i = windowSize; i < n; ++i) {
			// 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
			sum += cardPoints[i] - cardPoints[i - windowSize];
			minSum = min(minSum, sum);
		}
		return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minSum;
	}

	bool carPooling(vector<vector<int>>& trips, int capacity) {
		int numPassengers{};
		for (int i = 0; i <= 1000; i++) {
			//下车
			for (auto it = trips.begin(); it != trips.end();) {
				auto&& trip = *it;
				if (trip[2] == i) {
					numPassengers -= trip[0];
					it = trips.erase(it);
				}
				else
					it++;
			}
			//上车
			for (auto trip : trips) {
				if (trip[1] == i)
					numPassengers += trip[0];
				if (numPassengers > capacity)
					return false;
			}
		}
		return true;
	}

	int sumIndicesWithKSetBits(vector<int>& nums, int k) {
		int sum{};
		for (int i = 0; i < nums.size(); i++) {
			bitset<32> bs(i);
			if (bs.count() == k) {
				sum += nums[i];
			}
		}
		return sum;
	}

	int maximumNumberOfStringPairs(vector<string>& words) {
		int result{};
		int size = words.size();
		for (int i = 0; i < size; i++) {
			reverse(words[i].begin(), words[i].end());
			for (int j = i + 1; j < size; j++) {
				if (words[j] == words[i]) {
					++result;
					break;
				}
			}
		}
		return result;
	}

	int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
		int n = mat.size();
		int m = mat[0].size();
		unordered_map<int, pair<int, int>> mp;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				mp[mat[i][j]] = { i, j };
			}
		}
		vector<int> rowCnt(n, 0);
		vector<int> colCnt(m, 0);
		for (int i = 0; i < arr.size(); ++i) {
			auto& v = mp[arr[i]];
			++rowCnt[v.first];
			if (rowCnt[v.first] == m) {
				return i;
			}
			++colCnt[v.second];
			if (colCnt[v.second] == n) {
				return i;
			}
		}
		return -1;
	}

	vector<string> cellsInRange(string s) {
		vector<string> result;
		for (char i = s[0]; i <= s[3]; i++) {
			for (char j = s[1]; j <= s[4]; j++) {
				result.emplace_back(string{ i, j });
			}
		}
		return result;
	}

	bool isAcronym(vector<string>& words, string s) {
		string result;
		for (string word : words) {
			result.push_back(word[0]);
		}
		return result == s;
	}

	vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
		vector<vector<int>> result;
		int size{ (int)grid.size() };
		result.resize(size - 2);
		for (int i = 1; i < size - 1; i++) {
			result[i - 1].resize(size - 2);
			for (int j = 1; j < size - 1; j++) {
				vector<int> temp{ grid[i - 1][j - 1], grid[i - 1][j], grid[i - 1][j + 1],
					grid[i][j - 1], grid[i][j], grid[i][j + 1],
					grid[i + 1][j - 1], grid[i + 1][j], grid[i + 1][j + 1] };
				result[i - 1][j - 1] = *std::max_element(temp.begin(), temp.end());
			}
		}
		return result;
	}

	int numberOfEmployeesWhoMetTarget(vector<int>& hours, int target) {
		int number{};
		for (int hour : hours) {
			if (hour >= target)
				++number;
		}
		return number;
	}

	int differenceOfSums(int n, int m) {
		int sum{};
		for (int i = 1; i <= n; i++) {
			if (i % m == 0)
				sum += i;
		}
		return n * (n + 1) / 2 - sum * 2;
	}

	int countPairs(vector<int>& nums, int target) {
		int count{};
		for (int i = 0; i < nums.size(); i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums[i] + nums[j] < target)
					++count;
			}
		}
		return count;
	}

	//100121. 查找包含给定字符的单词
	vector<int> findWordsContaining(vector<string>& words, char x) {
		vector<int> result;
		for (int i = 0; i < words.size(); i++) {
			if (words[i].find(x) != string::npos)
				result.emplace_back(i);
		}
		return result;
	}

	int maximumStrongPairXor(vector<int>& nums) {
		int result{ INT_MIN };
		int size = nums.size();
		for (int i = 0; i < size; i++) {
			int x = nums[i];
			for (int j = i; j < size; j++) {
				int y = nums[j];
				if (abs(x - y) <= std::min(x, y))
					result = std::max(x ^ y, result);
			}
		}
		return result;
	}

	string oddString(vector<string>& words) {
		auto get = [](string& word) {
			vector<int> diff(word.size() - 1);
			for (int i = 0; i + 1 < word.size(); i++) {
				diff[i] = word[i + 1] - word[i];
			}
			return diff;
		};
		auto diff0 = get(words[0]);
		auto diff1 = get(words[1]);
		if (diff0 == diff1) {
			for (int i = 2; i < words.size(); i++) {
				if (diff0 != get(words[i])) {
					return words[i];
				}
			}
		}
		return diff0 == get(words[2]) ? words[1] : words[0];
	}

	int findMaxK(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		for (int i = nums.size() - 1; i >= 0; i--) {
			if (nums[i] < 0)
				return -1;
			if (binarySearch(nums.begin(), nums.begin() + i, -nums[i]) != -1)
				return nums[i];
		}
		return -1;
	}

	int countPoints(string rings) {
		int count{};
		vector<unordered_set<char>> hashTable(10);
		for (int i = 0; i < rings.length(); i += 2) {
			hashTable[rings[i + 1] - '0'].emplace(rings[i]);
		}
		for (int i = 0; i < 10; i++) {
			if (hashTable[i].size() == 3)
				++count;
		}
		return count;
	}

	int count{};

	//222. 完全二叉树的节点个数
	int countNodes(TreeNode* root) {
		if (!root)
			return count;
		++count;
		countNodes(root->left);
		countNodes(root->right);
		return count;
	}

	//2710. 移除字符串中的尾随零
	string removeTrailingZeros(string num) {
		for (int i = num.length() - 1; i >= 0; i--) {
			if (num[i] != '0')
				return { num.begin(), num.begin() + i + 1 };
		}
		return num;
	}

	//2644. 找出可整除性得分最大的整数
	int maxDivScore(vector<int>& nums, vector<int>& divisors) {
		int max{};
		int result{ INT_MAX };
		for (int divisor : divisors)
		{
			int count{};
			for (int num : nums)
			{
				if (num % divisor == 0)
					++count;
			}
			if (count > max)
			{
				max = count;
				result = divisor;
			}
			if (count == max && divisor < result)
				result = divisor;
		}
		return result;
	}

	//2485. 找出中枢整数
	int pivotInteger(int n) {
		int left{ 0 };
		int right{ ((n + 1) * n) >> 1 };
		for (int i = 1; i <= n; i++) {
			left += i;
			right -= i - 1;
			if (left == right)
				return i;
		}
		return -1;
	}

	//605. 种花问题
	bool canPlaceFlowers(vector<int>& flowerbed, int n) {
		for (int i = 0; i < flowerbed.size(); i++) {
			int last = i - 1 >= 0 ? flowerbed[i - 1] : 0;
			int next = i + 1 < flowerbed.size() ? flowerbed[i + 1] : 0;
			if (flowerbed[i] == 0 && last == 0 && next == 0) {
				--n;
				++i;
			}
			if (n <= 0)
				return true;
		}
		return false;
	}

	//LCP 06. 拿硬币
	int minCount(vector<int>& coins) {
		int count{};
		for (int coin : coins) {
			count += (coin >> 1);
			count += (coin & 0x1);
		}
		return count;
	}

	//2446. 判断两个事件是否存在冲突
	bool haveConflict(vector<string>& event1, vector<string>& event2) {
		return !(event1[1] < event2[0] || event2[1] < event1[0]);
	}

	//1957. 删除字符使字符串变好
	string makeFancyString(string s) {
		int len = s.length();
		if (s.length() < 3)
			return s;

		string result;
		for (int i = 0; i < len - 2; i++) {
			if (s[i] == s[i + 1] && s[i + 1] == s[i + 2])
				continue;
			result.push_back(s[i]);
		}
		result.push_back(s[len - 2]);
		result.push_back(s[len - 1]);
		return result;
	}

	//2562. 找出数组的串联值
	long long findTheArrayConcVal(vector<int>& nums) {
		long long result{};
		int n = nums.size();
		int n2 = n >> 1;
		for (int i = 0; i < n2; i++) {
			int last = nums[n - 1 - i];
			long long tmp = nums[i] * pow(10, to_string(last).length()) + last;
			result += tmp;
		}
		if ((n & 0b1) != 0)
			result += nums[n2];
		return result;
	}

	//2032. 至少在两个数组中出现的值
	vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
		int hashTable[100] = { 0 };
		auto&& uniqueVector = [&hashTable](vector<int>& nums) {
			sort(nums.begin(), nums.end());
			auto last = unique(nums.begin(), nums.end());
			for (auto it = nums.begin(); it != last; it++) {
				++hashTable[*it - 1];
			}
		};
		uniqueVector(nums1);
		uniqueVector(nums2);
		uniqueVector(nums3);

		vector<int> result;
		for (int i = 0; i < 100; i++) {
			if (hashTable[i] >= 2)
				result.emplace_back(i + 1);
		}
		return result;
	}

	//1961. 检查字符串是否为数组前缀
	bool isPrefixString(string s, vector<string>& words) {
		string prefix{};
		int len = s.length();
		for (int i = 0; i < words.size(); i++) {
			if (prefix.length() > len)
				break;
			prefix += words[i];
			if (prefix == s)	return true;
		}
		return false;
	}

	//746. 使用最小花费爬楼梯
	int minCostClimbingStairs(vector<int>& cost) {
		int n = cost.size();
		vector<int> dp(n + 1);
		dp[0] = dp[1] = 0;
		for (int i = 2; i <= n; i++) {
			dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
		}
		return dp[n];
	}

	//1624. 两个相同字符之间的最长子字符串
	int maxLengthBetweenEqualCharacters(string s) {
		int result{ -1 };
		unsigned short hashTable[26] = { 0 };
		for (int i = 0; i < s.length(); i++) {
			char c = s[i];
			int pos = hashTable[c - 'a'];
			if (pos == 0) {
				hashTable[c - 'a'] = i + 1;
			}
			else {
				result = std::max(i - pos, result);
			}
		}
		return result;
	}

	//2848. 与车相交的点
	int numberOfPoints(vector<vector<int>>& nums) {
		bool hashTable[100] = { false };
		for (const auto& num : nums) {
			for (int i = num[0]; i <= num[1]; i++) {
				hashTable[i - 1] = true;
			}
		}
		int result{};
		for (int i = 0; i < 100; i++) {
			if (hashTable[i])
				++result;
		}
		return result;
	}

	//2367. 算术三元组的数目
	int arithmeticTriplets(vector<int>& nums, int diff) {
		int result{};
		for (int i = 1; i < nums.size() - 1; i++) {
			int dis = binarySearch(nums.begin(), nums.begin() + i, nums[i] - diff);
			if (dis == -1) continue;
			dis = binarySearch(nums.begin() + (i + 1), nums.end(), nums[i] + diff);
			if (dis == -1) continue;
			++result;
		}
		return result;
	}

	//2594. 修车的最少时间
	long long repairCars(vector<int>& ranks, int cars) {
		using ll = long long;
		ll l = 1, r = 1ll * ranks[0] * cars * cars;
		auto check = [&](ll m) {
			ll cnt = 0;
			for (auto x : ranks) {
				cnt += sqrt(m / x);
			}
			return cnt >= cars;
		};
		while (l < r) {
			ll m = l + (r >> 1);
			if (check(m)) {
				r = m;
			}
			else {
				l = m + 1;
			}
		}
		return l;
	}

	//LCR 002. 二进制求和
	string addBinary(string a, string b) {
		string ans;
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());

		int n = max(a.size(), b.size()), carry = 0;
		for (size_t i = 0; i < n; ++i) {
			carry += i < a.size() ? (a.at(i) == '1') : 0;
			carry += i < b.size() ? (b.at(i) == '1') : 0;
			ans.push_back((carry % 2) ? '1' : '0');
			carry /= 2;
		}

		if (carry) {
			ans.push_back('1');
		}
		reverse(ans.begin(), ans.end());

		return ans;
	}

	//1071. 字符串的最大公因子
	string gcdOfStrings(string str1, string str2) {
		auto&& check = [](string t, string s) {
			int lenx = (int)s.length() / (int)t.length();
			string ans = "";
			for (int i = 1; i <= lenx; ++i) {
				ans = ans + t;
			}
			return ans == s;
		};
		int len1 = (int)str1.length(), len2 = (int)str2.length();
		for (int i = min(len1, len2); i >= 1; --i) { // 从长度大的开始枚举
			if (len1 % i == 0 && len2 % i == 0) {
				string X = str1.substr(0, i);
				if (check(X, str1) && check(X, str2)) return X;
			}
		}
		return "";
	}

	//1921. 消灭怪物的最大数量
	int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
		int n = dist.size();
		vector<int> arrivalTimes(n);
		for (int i = 0; i < n; i++) {
			arrivalTimes[i] = (dist[i] - 1) / speed[i] + 1;
		}
		sort(arrivalTimes.begin(), arrivalTimes.end());
		for (int i = 0; i < n; i++) {
			if (arrivalTimes[i] <= i) {
				return i;
			}
		}
		return n;
	}

	//2511. 最多可以摧毁的敌人城堡数目
	int captureForts(vector<int>& forts) {
		int ans = 0, pre = -1;
		for (int i = 0; i < forts.size(); i++) {
			if (forts[i] == 1 || forts[i] == -1) {
				if (pre >= 0 && forts[i] != forts[pre]) {
					ans = max(ans, i - pre - 1);
				}
				pre = i;
			}
		}
		return ans;
	}

	//LCP 50. 宝石补给
	int giveGem(vector<int>& gem, vector<vector<int>>& operations) {
		for (const auto& operation : operations) {
			int x = operation[0];
			int y = operation[1];
			int n = floor(gem[x] / 2);
			gem[x] -= n;
			gem[y] += n;
		}
		return *max_element(gem.begin(), gem.end()) - *min_element(gem.begin(), gem.end());
	}

	//2833. 距离原点最远的点
	int furthestDistanceFromOrigin(string moves) {
		int distance{};
		int count{};
		for (char move : moves) {
			if (move == 'L')
				--distance;
			else if (move == 'R')
				++distance;
			else
				++count;
		}
		return std::abs(distance) + count;
	}

	//2240. 买钢笔和铅笔的方案数
	long long waysToBuyPensPencils(int total, int cost1, int cost2) {
		long long result{};
		while (total >= 0) {
			result += total / cost2 + 1;
			total -= cost1;
		}
		return result;
	}

	//495. 提莫攻击
	int findPoisonedDuration(vector<int>& timeSeries, int duration) {
		int result{ duration };
		for (int i = 0; i < timeSeries.size() - 1; i++)
			result += std::min(duration, timeSeries[i + 1] - timeSeries[i]);
		return result;
	}

	//1763. 最长的美好子字符串
	string longestNiceSubstring(string s) {
		int n = s.size();
		int maxPos = 0;
		int maxLen = 0;
		for (int i = 0; i < n; ++i) {
			int lower = 0;
			int upper = 0;
			for (int j = i; j < n; ++j) {
				if (islower(s[j])) {
					lower |= 1 << (s[j] - 'a');
				}
				else {
					upper |= 1 << (s[j] - 'A');
				}
				if (lower == upper && j - i + 1 > maxLen) {
					maxPos = i;
					maxLen = j - i + 1;
				}
			}
		}
		return s.substr(maxPos, maxLen);
	}

	//2303. 计算应缴税款总额
	double calculateTax(vector<vector<int>>& brackets, int income) {
		double result{};
		int last{};
		for (int i = 0; i < brackets.size(); i++) {
			auto&& bracket = brackets[i];
			if (income > bracket[0])
				result += (bracket[0] - last) * bracket[1];
			else {
				result += (income - last) * bracket[1];
				break;
			}
			last = bracket[0];
		}
		return result * 0.01;
	}

	//2784. 检查数组是否是好的
	bool isGood(vector<int>& nums) {
		int size = nums.size();
		if (size < 2)
			return false;
		sort(nums.begin(), nums.end());
		for (int i = 0; i < size - 1; i++) {
			if (nums[i] != i + 1)
				return false;
		}
		if (nums[size - 2] != nums[size - 1])
			return false;
		return nums[size - 1] == size - 1;
	}

	//2248. 多个数组求交集
	vector<int> intersection(vector<vector<int>>& nums) {
		int hashTable[1000] = {};
		for (const auto& num : nums) {
			for (int n : num)
				++hashTable[n - 1];
		}
		vector<int> result;
		int size = nums.size();
		for (int i = 0; i < 1000; i++) {
			if (hashTable[i] == size)
				result.emplace_back(i + 1);
		}
		return result;
	}

	//1399. 统计最大组的数目
	int countLargestGroup(int n) {
		unordered_map<int, int> hashMap;
		int maxValue = 0;
		for (int i = 1; i <= n; ++i) {
			int key = 0, i0 = i;
			while (i0) {
				key += i0 % 10;
				i0 /= 10;
			}
			++hashMap[key];
			maxValue = max(maxValue, hashMap[key]);
		}
		int count = 0;
		for (auto& kvpair : hashMap) {
			if (kvpair.second == maxValue) {
				++count;
			}
		}
		return count;
	}

	//2525. 根据规则将箱子分类
	string categorizeBox(int length, int width, int height, int mass) {
		long long volume{ (long long)length * width * height };
		bool result[2] = { false, false };
		if ((length >= 10000 || width >= 10000 || height >= 10000) || volume >= 1000000000)
			result[0] = true;
		if (mass >= 100)
			result[1] = true;
		if (result[0] && result[1])
			return "Both";
		else if (result[0])
			return "Bulky";
		else if (result[1])
			return "Heavy";
		return "Neither";
	}

	//2558. 从数量最多的堆取走礼物
	long long pickGifts(vector<int>& gifts, int k) {
		for (int i = 0; i < k; i++) {
			nth_element(gifts.begin(), gifts.begin(), gifts.end(), std::greater<int>());
			gifts[0] = floor(sqrt(gifts[0]));
		}
		return accumulate(gifts.begin(), gifts.end(), (long long)0);
	}

	//1507. 转变日期格式
	string reformatDate(string date) {
		auto&& result = splitString(date.c_str(), " ");
		char buffer[20];
		std::sprintf(buffer, "%s-%02d-%02d", result[2].c_str(), monthToInt(result[1]), dayToInt(result[0]));
		return buffer;
	}

	//1417. 重新格式化字符串
	string reformat(string s) {
		queue<char> q1, q2;
		for (char c : s) {
			if (isdigit(c))
				q1.push(c);
			else
				q2.push(c);
		}

		if (q1.size() < q2.size())
			swap(q1, q2);

		if (q1.size() - q2.size() > 1)
			return "";

		string result;
		while (!q2.empty()) {
			result.push_back(q1.front()); q1.pop();
			result.push_back(q2.front()); q2.pop();
		}
		if (!q1.empty())
			result.push_back(q1.front());
		return result;
	}

	//2591. 将钱分给最多的儿童
	int distMoney(int money, int children) {
		money -= children;
		int tmp = children * 7;
		if (money < 0) return -1;
		if (money > tmp) return children - 1;
		if (money == tmp) return children;
		if (money == tmp - 4) return children - 2;
		return money / 7;
	}

	//997. 找到小镇的法官
	int findJudge(int n, vector<vector<int>>& trust) {
		std::unordered_map<int, vector<int>> hashTable;
		for (const auto& t : trust) {
			hashTable[t[1]].emplace_back(t[0]);
		}
		for (int i = 1; i <= n; i++) {
			auto it = std::find_if(trust.begin(), trust.end(), [i](const auto& t) { return t[0] == i; });
			if (it != trust.end())
				continue;
			if (hashTable[i].size() != n - 1)
				continue;
			return i;
		}
		return -1;
	}

	//1556. 千位分隔数
	string thousandSeparator(int n) {
		string result{ to_string(n) };
		for (int i = result.length() - 3; i >= 1; i -= 3) {
			result.insert(result.begin() + i, '.');
		}
		return result;
	}

	//2733. 既不是最小值也不是最大值
	int findNonMinOrMax(vector<int>& nums) {
		if (nums.size() < 3)
			return -1;
		nth_element(nums.begin(), nums.begin() + 1, nums.end());
		return nums[1];
	}

	//1608. 特殊数组的特征值
	int specialArray(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		for (int i = 1; i <= nums.size(); i++) {
			auto it = std::lower_bound(nums.begin(), nums.end(), i);
			if (i == distance(it, nums.end()))
				return i;
		}
		return -1;
	}

	//1909. 删除一个元素使数组严格递增
	bool canBeIncreasing(vector<int>& nums) {
		int i = isIncreasing(nums);
		if (i == -1)
			return true;
		vector<int> temp{ nums };
		nums.erase(nums.begin() + i);
		i = isIncreasing(nums);
		if (i == -1)
			return true;
		temp.erase(temp.begin() + i - 1);
		i = isIncreasing(temp);
		if (i == -1)
			return true;
		return false;
	}

	//2578. 最小和分割
	int splitNum(int num) {
		string s{ to_string(num) };
		sort(s.begin(), s.end());
		string num1, num2;
		for (int i = 0; i < s.length(); i++) {
			if (s[i] == '0')
				continue;
			if (i % 2 == 0)
				num1.push_back(s[i]);
			else
				num2.push_back(s[i]);
		}
		return (num1 != "" ? stoi(num1) : 0) + (num2 != "" ? stoi(num2) : 0);
	}

	//2810. 故障键盘
	string finalString(string s) {
		string result;
		for (char c : s) {
			if (c == 'i')
				reverse(result.begin(), result.end());
			else
				result.push_back(c);
		}
		return result;
	}

	//2769. 找出最大的可达成数字
	int theMaximumAchievableX(int num, int t) {
		return num + t * 2;
	}

	//2409. 统计共同度过的日子数
	int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
		int arriveAliceDay = calculateDayOfYear(arriveAlice);
		int leaveAliceDay = calculateDayOfYear(leaveAlice);
		int arriveBobDay = calculateDayOfYear(arriveBob);
		int leaveBobDay = calculateDayOfYear(leaveBob);
		return max(0, min(leaveAliceDay, leaveBobDay) - max(arriveAliceDay, arriveBobDay) + 1);
	}

	//2129. 将标题首字母大写
	string capitalizeTitle(string title) {
		auto&& result = splitString(title.c_str(), " ");
		for (string& str : result) {
			if (str.length() <= 2)
				str = stringToLower(str);
			else
				str = stringToTitle(str);
		}
		return combinString(result, " ");
	}

	//2682. 找出转圈游戏输家
	vector<int> circularGameLosers(int n, int k) {
		bool hashTable[50] = { true };
		int pos{};
		for (int i = 1;; i++) {
			pos += i * k;
			pos %= n;
			if (hashTable[pos])
				break;
			else
				hashTable[pos] = true;
		}
		vector<int> result;
		for (int i = 0; i < n; i++) {
			if (!hashTable[i])
				result.emplace_back(i + 1);
		}
		return result;
	}

	//2335. 装满杯子需要的最短总时长
	int fillCups(vector<int>& amount) {
		int time{};
		while (amount[0] != 0 || amount[1] != 0 || amount[2] != 0) {
			sort(amount.begin(), amount.end());
			if (amount[1] != 0) {
				--amount[1];
				--amount[2];
			}
			else
				--amount[2];
			++time;
		}
		return time;
	}

	//2176. 统计数组中相等且可以被整除的数对
	/*int countPairs(vector<int>& nums, int k) {
		int count{};
		for (int i = 0; i < nums.size(); i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums[i] == nums[j] && (i * j) % k == 0)
					++count;
			}
		}
		return count;
	}*/

	//1582. 二进制矩阵中的特殊位置
	bool isSpecial(vector<vector<int>>& mat, int m, int n) {
		for (int i = 0; i < mat.size(); i++) {
			if (i != m && mat[i][n] == 1)
				return false;
		}
		for (int i = 0; i < mat[0].size(); i++) {
			if (i != n && mat[m][i] == 1)
				return false;
		}
		return true;
	}

	int numSpecial(vector<vector<int>>& mat) {
		int num{};
		for (int i = 0; i < mat.size(); i++) {
			for (int j = 0; j < mat[i].size(); j++) {
				if (mat[i][j] == 1 && isSpecial(mat, i, j))
					++num;
			}
		}
		return num;
	}

	//617. 合并二叉树
	void mergeTrees(TreeNode* root1, TreeNode* root2, TreeNode* root) {
		if (!root1 && !root2)
			return;
		root->val = (root1 ? root1->val : 0) + (root2 ? root2->val : 0);
		if ((root1 && root1->left) || (root2 && root2->left)) {
			root->left = new TreeNode(0);
			mergeTrees(root1 ? root1->left : nullptr, root2 ? root2->left : nullptr, root->left);
		}
		if ((root1 && root1->right) || (root2 && root2->right)) {
			root->right = new TreeNode(0);
			mergeTrees(root1 ? root1->right : nullptr, root2 ? root2->right : nullptr, root->right);
		}
	}

	TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
		if (!root1 && !root2)
			return nullptr;
		TreeNode* root = new TreeNode(0);
		mergeTrees(root1, root2, root);
		return root;
	}

	//1572. 矩阵对角线元素的和
	/*int diagonalSum(vector<vector<int>>& mat) {
		int sum{};
		int size{ (int)mat.size() };
		for (int i = 0; i < size; i++) {
			sum += mat[i][i];
		}
		for (int i = 0; i < size; i++) {
			int j{ size - 1 - i };
			if (i != j)
				sum += mat[i][j];
		}
		return sum;
	}*/

	//1945. 字符串转化后的各位数字之和
	int getLucky(string s, int k) {
		string temp = "";
		for (char c : s) {
			int v = c - 'a' + 1;
			temp += to_string(v);
		}

		int sum{};
		for (int i = 0; i < k; i++) {
			sum = 0;
			for (char c : temp) {
				sum += c - '0';
			}
			temp = to_string(sum);
		}
		return sum;
	}

	//1281. 整数的各位积和之差
	int subtractProductAndSum(int n) {
		int product{ 1 };
		int sum{ 0 };
		for (char c : to_string(n)) {
			int v = c - '0';
			product *= v;
			sum += v;
		}
		return product - sum;
	}

	//1496. 判断路径是否相交
	bool isPathCrossing(string path) {
		vector<vector<int>> hashTable;
		hashTable.push_back({ 0, 0 });

		vector<int> start{ 0, 0 };
		for (char c : path) {
			if (c == 'N')
				++start[1];
			else if (c == 'S')
				--start[1];
			else if (c == 'E')
				++start[0];
			else if (c == 'W')
				--start[0];
			if (std::find_if(hashTable.begin(), hashTable.end(), [&start](vector<int> point) {
				return point[0] == start[0] && point[1] == start[1];
				}) != hashTable.end())
				return true;
			else
				hashTable.emplace_back(start);
			//cout << start[0] << start[1] << endl;
		}
		return false;
	}

	//2706. 购买两块巧克力
	int buyChoco(vector<int>& prices, int money) {
		nth_element(prices.begin(), prices.begin() + 1, prices.end());
		int sum = prices[0] + prices[1];
		return sum > money ? money : money - sum;
	}

	//28. 找出字符串中第一个匹配项的下标
	int strStr(string haystack, string needle) {
		return haystack.find(needle);
	}

	//860. 柠檬水找零
	bool lemonadeChange(vector<int>& bills) {
		int hashTable[4] = { 0 };
		for (int bill : bills) {
			if (bill == 10) {
				if (hashTable[0] == 0)
					return false;
				else
					--hashTable[0];
			}
			else if (bill == 20) {
				if (hashTable[1] > 0 && hashTable[0] > 0) {
					--hashTable[1];
					--hashTable[0];
				}
				else if (hashTable[0] > 2) {
					hashTable[0] -= 3;
				}
				else
					return false;
			}
			++hashTable[bill / 5 - 1];
		}
		return true;
	}

	//2379. 得到 K 个黑块的最少涂色次数
	int minimumRecolors(string blocks, int k) {
		int l = 0, r = 0, cnt = 0;
		while (r < k) {
			cnt += blocks[r] == 'W' ? 1 : 0;
			r++;
		}
		int res = cnt;
		while (r < blocks.size()) {
			cnt += blocks[r] == 'W' ? 1 : 0;
			cnt -= blocks[l] == 'W' ? 1 : 0;
			res = min(res, cnt);
			l++;
			r++;
		}
		return res;
	}

	//2293. 极大极小游戏
	int minMaxGame(vector<int>& nums) {
		while (nums.size() > 1) {
			vector<int> newNums;
			for (int i = 0; i < nums.size() / 2; i++) {
				if (i % 2 == 0)
					newNums.emplace_back(min(nums[2 * i], nums[2 * i + 1]));
				else
					newNums.emplace_back(max(nums[2 * i], nums[2 * i + 1]));
			}
			nums = newNums;
		}
		return nums[0];
	}

	//1518. 换水问题
	int numWaterBottles(int numBottles, int numExchange) {
		int result{};
		int numEmpty{};
		while (numBottles + numEmpty >= numExchange) {
			result += numBottles; //喝水
			int numEmptys{ numBottles + numEmpty };
			numBottles = numEmptys / numExchange;
			numEmpty = numEmptys % numExchange;
			//cout << numBottles << " " << numEmpty << endl;
		}
		result += numBottles;
		return result;
	}

	//415. 字符串相加
	string addStrings(string num1, string num2) {
		string result;
		reverse(num1.begin(), num1.end());
		reverse(num2.begin(), num2.end());
		int carry{ 0 };
		for (int i = 0; i < num1.length() || i < num2.length() || carry != 0; i++) {
			int a = i < num1.length() ? num1[i] - '0' : 0;
			int b = i < num2.length() ? num2[i] - '0' : 0;
			//cout << a << " " << b << endl;
			int sum = a + b + carry;
			carry = sum / 10;
			result.push_back(sum % 10 + '0');
		}
		reverse(result.begin(), result.end());
		return result;
	}

	//2243. 计算字符串的数字和
	string digitSum(string s, int k) {
		while (s.length() > k) {
			string result = "";
			for (int i = 0; i < s.length(); i += k) {
				auto it = i + k >= s.length() ? s.end() : s.begin() + i + k;
				string temp(s.begin() + i, it);
				//cout<< temp.c_str() <<endl;

				int sum{};
				for (char c : temp) {
					sum += c - '0';
				}
				result += to_string(sum);
			}
			s = result;
		}
		return s;
	}

	//2215. 找出两数组的不同
	vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
		unordered_set<int> set1(nums1.begin(), nums1.end());
		unordered_set<int> set2(nums2.begin(), nums2.end());
		for (auto it1 = set1.begin(); it1 != set1.end();) {
			auto it2 = set2.find(*it1);
			if (it2 != set2.end()) {
				it1 = set1.erase(it1);
				set2.erase(it2);
			}
			else
				++it1;
		}
		return { {set1.begin(), set1.end()}, {set2.begin(), set2.end()} };
	}

	//2269. 找到一个数字的 K 美丽值
	int divisorSubstrings(int num, int k) {
		int res{};
		string str = to_string(num);
		for (int i = 0; i < str.length() - k + 1; i++) {
			string temp(str.begin() + i, str.begin() + i + k);
			int value{ stoi(temp) };
			if (value != 0 && num % value == 0)
				++res;
		}
		return res;
	}

	//2078. 两栋颜色不同且距离最远的房子
	int maxDistance(vector<int>& colors) {
		int distance{};
		for (int i = 0; i < colors.size(); i++) {
			for (int j = colors.size() - 1; j >= 0; j--) {
				if (colors[j] != colors[i]) {
					int dis = j - i;
					distance = std::max(dis, distance);
				}
			}
		}
		return distance;
	}

	//2652. 倍数求和
	int sumOfMultiples(int n) {
		int result{};
		for (int i = 1; i <= n; i++) {
			if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
				result += i;
		}
		return result;
	}

	//2643. 一最多的行
	vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
		vector<int> result{ 0,0 };
		for (int i = 0; i < mat.size(); i++) {
			int num{ 0 };
			for (int j = 0; j < mat[i].size(); j++) {
				if (mat[i][j] == 1)
					++num;
			}
			if (num > result[1]) {
				result[0] = i;
				result[1] = num;
			}
		}
		return result;
	}

	//2605. 从两个数字数组里生成最小数字
	int minNumber(vector<int>& nums1, vector<int>& nums2) {
		int hashTable[9] = { 0 };
		for (int num : nums1)
			++hashTable[num - 1];
		for (int num : nums2)
			++hashTable[num - 1];
		for (int i = 0; i < 9; i++) {
			if (hashTable[i] == 2)
				return i + 1;
		}

		int num1 = *min_element(nums1.begin(), nums1.end());
		int num2 = *min_element(nums2.begin(), nums2.end());
		if (num1 < num2)
			return num1 * 10 + num2;
		else
			return num2 * 10 + num1;
	}

	//2239. 找到最接近 0 的数字
	int findClosestNumber(vector<int>& nums) {
		sort(nums.begin(), nums.end());

		if (nums[0] >= 0)
			return nums[0];

		int size{ (int)nums.size() };
		if (nums[size - 1] <= 0)
			return nums[size - 1];

		for (int i = 0; i < size - 1; i++) {
			int current{ nums[i] };
			int next{ nums[i + 1] };
			if (current <= 0 && next >= 0)
				return next <= -current ? next : current;
		}
		return 0;
	}

	//2600. K 件物品的最大和
	int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
		if (k <= numOnes)
			return k;
		if (k <= numOnes + numZeros)
			return numOnes;
		return numOnes - (k - numOnes - numZeros);
	}

	//2679. 矩阵中的和
	int matrixSum(vector<vector<int>>& nums) {
		for (int i = 0; i < nums.size(); i++)
			sort(nums[i].begin(), nums[i].end());
		int result{};
		for (int i = 0; i < nums[0].size(); i++) {
			int value{};
			for (int j = 0; j < nums.size(); j++)
				value = std::max(nums[j][i], value);
			result += value;
		}
		return result;
	}

	//2119. 反转两次的数字
	bool isSameAfterReversals(int num) {
		if (num == 0)
			return true;
		return num % 10 != 0;
	}

	//2169. 得到 0 的操作数
	int countOperations(int num1, int num2) {
		int result{};
		while (num1 != 0 && num2 != 0) {
			if (num1 >= num2)
				num1 -= num2;
			else
				num2 -= num1;
			++result;
		}
		return result;
	}

	//2. 两数相加
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode* result{ new ListNode(-1) };
		ListNode* node{ result };

		int carry{};
		while (l1 || l2 || carry) {
			if (node->val != -1) {
				node->next = new ListNode(-1);
				node = node->next;
			}

			int val1 = l1 ? l1->val : 0;
			int val2 = l2 ? l2->val : 0;
			node->val = (val1 + val2 + carry) % 10;
			carry = (val1 + val2 + carry) / 10;

			l1 = l1 ? l1->next : nullptr;
			l2 = l2 ? l2->next : nullptr;
		}
		return result;
	}

	//2656. K 个元素的最大和
	int maximizeSum(vector<int>& nums, int k) {
		int max = *max_element(nums.begin(), nums.end());
		int sum = 0;
		for (int i = 0; i < k; i++)
			sum += max + i;
		return sum;
	}

	//2309. 兼具大小写的最好英文字母
	string greatestLetter(string s) {
		bool arr1[26] = { false };
		bool arr2[26] = { false };
		for (char c : s) {
			if (isupper(c))
				arr1[c - 'A'] = true;
			else
				arr2[c - 'a'] = true;
		}
		for (int i = 25; i >= 0; i--) {
			if (arr1[i] && arr2[i])
				return string(1, i + 'A');
		}
		return "";
	}

	//2460. 对数组执行操作
	vector<int> applyOperations(vector<int>& nums) {
		int n = nums.size();
		for (int i = 0, j = 0; i < n; i++) {
			if (i + 1 < n && nums[i] == nums[i + 1]) {
				nums[i] *= 2;
				nums[i + 1] = 0;
			}
			if (nums[i] != 0) {
				swap(nums[i], nums[j]);
				j++;
			}
		}
		return nums;
	}

	//1952. 三除数
	bool isThree(int n) {
		if (n <= 1)
			return false;
		int count{};
		for (int i = 2; i < n; i++) {
			if (n % i == 0)
				++count;
		}
		return count == 1;
	}

	//2678. 老人的数目
	int countSeniors(vector<string>& details) {
		int count{};
		for (const auto& detail : details) {
			string age(detail, 11, 2);
			if (stoi(age) > 60)
				++count;
		}
		return count;
	}

	//2651. 计算列车到站时间
	int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
		return (arrivalTime + delayedTime) % 24;
	}

	//2432. 处理用时最长的那个任务的员工
	int hardestWorker(int n, vector<vector<int>>& logs) {
		for (int i = logs.size() - 1; i >= 1; i--)
			logs[i][1] = logs[i][1] - logs[i - 1][1];
		sort(logs.begin(), logs.end(), [](const auto& a, const auto& b) {
			if (a[1] == b[1])
				return a[0] < b[0];
			return a[1] > b[1];
			});
		return logs[0][0];
	}

	//2395. 和相等的子数组
	bool findSubarrays(vector<int>& nums) {
		unordered_set<int> temp;
		for (int i = 0; i < (int)nums.size() - 1; i++) {
			int sum = nums[i] + nums[i + 1];
			if (temp.find(sum) != temp.end())
				return true;
			else
				temp.insert(sum);
		}
		return false;
	}

	//2544. 交替数字和
	int alternateDigitSum(int n) {
		int res{};
		string str = to_string(n);
		for (int i = 0; i < str.length(); i++) {
			int value = str[i] - '0';
			res += value * (i % 2 == 0 ? 1 : -1);
		}
		return res;
	}

	//2190. 数组中紧跟 key 之后出现最频繁的数字
	int mostFrequent(vector<int>& nums, int key) {
		int hashTable[1000] = { 0 };
		for (int i = 0; i < nums.size() - 1; i++) {
			if (nums[i] == key)
				++hashTable[nums[i + 1] - 1];
		}
		int n{ INT_MIN };
		int res{};
		for (int i = 0; i < 1000; i++) {
			if (hashTable[i] > n) {
				res = i + 1;
				n = hashTable[i];
			}
		}
		return res;
	}

	//2427. 公因子的数目
	int commonFactors(int a, int b) {
		int num{};
		for (int i = 1; i <= min(a, b); i++) {
			if (a % i == 0 && b % i == 0)
				++num;
		}
		return num;
	}

	//2006. 差的绝对值为 K 的数对数目
	int countKDifference(vector<int>& nums, int k) {
		int res{};
		for (int i = 0; i < nums.size() - 1; i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (abs(nums[i] - nums[j]) == k)
					++res;
			}
		}
		return res;
	}

	//1608. 特殊数组的特征值
	/*int specialArray(vector<int>& nums) {
		sort(nums.begin(), nums.end(), greater<int>());
		int n = nums.size();
		for (int i = 1; i <= n; ++i) {
			if (nums[i - 1] >= i && (i == n || nums[i] < i)) {
				return i;
			}
		}
		return -1;
	}*/

	//剑指 Offer II 068. 查找插入位置
	int searchInsert(vector<int>& nums, int target) {
		int index = lowerBound(nums.begin(), nums.end(), target);
		return index != -1 ? index : nums.size();
	}

	//LCP 28. 采购方案
	int purchasePlans(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());
		int res{};
		for (int i = 0; i < nums.size() - 1; i++) {
			int index = upperBound(nums.begin() + i + 1, nums.end(), target - nums[i]);
			res += index != -1 ? index : nums.size() - i - 1;
			res %= 1000000007;
		}
		return res;
	}

	//LCP 18. 早餐组合
	int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) {
		sort(staple.begin(), staple.end());
		sort(drinks.begin(), drinks.end());

		int res{};
		for (int n : staple) {
			int index = upperBound(drinks.begin(), drinks.end(), x - n);
			res += index != -1 ? index : drinks.size();
			res %= 1000000007;
		}
		return res;
	}

	//2540. 最小公共值
	int getCommon(vector<int>& nums1, vector<int>& nums2) {
		for (int num : nums1) {
			int index = binarySearch(nums2.begin(), nums2.end(), num);
			if (index != -1)
				return num;
		}
		return -1;
	}

	//1437. 是否所有 1 都至少相隔 k 个元素
	bool kLengthApart(vector<int>& nums, int k) {
		int last{ -1 };
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] == 1) {
				if (last != -1 && i - last <= k)
					return false;
				last = i;
			}
		}
		return true;
	}

	//2363. 合并相似的物品
	vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
		for (const auto& item : items2) {
			auto it = find_if(items1.begin(), items1.end(), [&](const vector<int>& value) {
				return value[0] == item[0];
				});
			if (it != items1.end())
				(*it)[1] += item[1];
			else
				items1.emplace_back(item);
		}
		sort(items1.begin(), items1.end(), [](auto& a, auto& b) { return a[0] < b[0]; });
		return items1;
	}

	//2099. 找到和最大的长度为 K 的子序列
	vector<int> maxSubsequence(vector<int>& nums, int k) {
		int n = nums.size();
		vector<pair<int, int>> vals;   // 辅助数组
		for (int i = 0; i < n; ++i) {
			vals.emplace_back(i, nums[i]);
		}
		// 按照数值降序排序
		sort(vals.begin(), vals.end(), [&](auto x1, auto x2) {
			return x1.second > x2.second;
			});
		// 取前 k 个并按照下标升序排序
		sort(vals.begin(), vals.begin() + k);
		vector<int> res;   // 目标子序列
		for (int i = 0; i < k; ++i) {
			res.push_back(vals[i].second);
		}
		return res;
	}

	//2389. 和有限的最长子序列
	vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
		sort(nums.begin(), nums.end());
		for (int i = 1; i < nums.size(); i++)
			nums[i] += nums[i - 1];
		for (int i = 0; i < queries.size(); i++) {
			if (nums[0] > queries[i]) {
				queries[i] = 0;
				continue;
			}

			for (int j = nums.size() - 1; j >= 0; j--) {
				if (nums[j] <= queries[i]) {
					queries[i] = j + 1;
					break;
				}
			}
		}
		return queries;
	}

	//2144. 打折购买糖果的最小开销
	int minimumCost(vector<int>& cost) {
		int size = (int)cost.size();
		if (size < 3)
			return accumulate(cost.begin(), cost.end(), 0);
		sort(cost.begin(), cost.end());
		int res{};
		for (int i = size - 3; i >= 0; i -= 3) {
			res += (cost[i + 1] + cost[i + 2]);
			if (i < 3)
				res = accumulate(cost.begin(), cost.begin() + i, res);
		}
		return res;
	}

	//2465. 不同的平均值数目
	int distinctAverages(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		unordered_set<float> res;
		for (int i = 0; i < nums.size() / 2; i++) {
			res.emplace((nums[i] + nums[nums.size() - 1 - i]) / 2.0);
		}
		return res.size();
	}

	//2164. 对奇偶下标分别排序
	vector<int> sortEvenOdd(vector<int>& nums) {
		vector<int> odd;
		vector<int> even;
		for (int i = 0; i < nums.size(); i++) {
			if (i % 2 == 0)
				even.emplace_back(nums[i]);
			else
				odd.emplace_back(nums[i]);
		}
		sort(odd.begin(), odd.end(), std::greater<int>());
		sort(even.begin(), even.end());
		for (int i = 0; i < nums.size(); i++) {
			if (i % 2 == 0)
				nums[i] = even[i / 2];
			else
				nums[i] = odd[(i - 1) / 2];
		}
		return nums;
	}

	//2154. 将找到的值乘以 2
	int findFinalValue(vector<int>& nums, int original) {
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] == original)
				original *= 2;
		}
		return original;
	}

	//2094. 找出 3 位偶数
	vector<int> findEvenNumbers(vector<int>& digits) {
		unordered_set<int> nums;   // 目标偶数集合
		int n = digits.size();
		// 遍历三个数位的下标
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				for (int k = 0; k < n; ++k) {
					// 判断是否满足目标偶数的条件
					if (i == j || j == k || i == k) {
						continue;
					}
					int num = digits[i] * 100 + digits[j] * 10 + digits[k];
					if (num >= 100 && num % 2 == 0) {
						nums.insert(num);
					}
				}
			}
		}
		// 转化为升序排序的数组
		vector<int> res;
		for (const int num : nums) {
			res.push_back(num);
		}
		sort(res.begin(), res.end());
		return res;
	}

	//2574. 左右元素和的差值
	vector<int> leftRigthDifference(vector<int>& nums) {
		int sum = accumulate(nums.begin(), nums.end(), 0);

		int leftSum{}, rightSum{};
		vector<int> result;
		for (int i = 0; i < nums.size(); i++) {
			rightSum = sum - nums[i] - leftSum;
			result.emplace_back(abs(rightSum - leftSum));
			leftSum += nums[i];
		}
		return result;
	}

	//LCP 66. 最小展台数量
	int minNumBooths(vector<string>& demand) {
		for (int i = 0; i < demand.size() - 1; i++) {
			sort(demand[i].begin(), demand[i].end());
			sort(demand[i + 1].begin(), demand[i + 1].end());

			vector<char> dest1;
			set_union(demand[i].begin(), demand[i].end(),
				demand[i + 1].begin(), demand[i + 1].end(), std::back_inserter(dest1));
			demand[i + 1] = string(dest1.begin(), dest1.end());
		}
		return demand[demand.size() - 1].size();
	}

	//2341. 数组能形成多少数对
	vector<int> numberOfPairs(vector<int>& nums) {
		int hashTable[101] = { 0 };
		for (int num : nums)
			++hashTable[num];

		vector<int> result{ 0, 0 };
		for (int i = 0; i <= 100; i++) {
			if (hashTable[i] != 0) {
				result[0] += (hashTable[i] >> 1);
				result[1] += (hashTable[i] & 1);
			}
		}
		return result;
	}

	//2347. 最好的扑克手牌
	string bestHand(vector<int>& ranks, vector<char>& suits) {
		suits.erase(unique(suits.begin(), suits.end()), suits.end());
		if (suits.size() == 1)
			return "Flush";
		int hashTable[13] = { 0 };
		string result = "High Card";
		for (int rank : ranks) {
			++hashTable[rank - 1];
			if (hashTable[rank - 1] >= 3)
				return "Three of a Kind";
			else if (hashTable[rank - 1] >= 2)
				result = "Pair";
		}
		return result;
	}

	//2037. 使每位学生都有座位的最少移动次数
	int minMovesToSeat(vector<int>& seats, vector<int>& students) {
		sort(seats.begin(), seats.end());
		sort(students.begin(), students.end());

		int result{};
		for (int i = 0; i < seats.size(); i++)
			result += abs(students[i] - seats[i]);
		return result;
	}

	//2496. 数组中字符串的最大值
	int maximumValue(vector<string>& strs) {
		int result{ INT_MIN };
		for (string str : strs) {
			bool digit{ true };
			for (char c : str) {
				if (!isdigit(c)) {
					digit = false;
					break;
				}
			}
			int len = digit ? atoi(str.c_str()) : str.length();
			result = max(len, result);
		}
		return result;
	}

	//2553. 分割数组中数字的数位
	vector<int> separateDigits(vector<int>& nums) {
		vector<int> result;
		for (int num : nums) {
			for (char c : to_string(num))
				result.emplace_back(c - '0');
		}
		return result;
	}

	//2455. 可被三整除的偶数的平均值
	int averageValue(vector<int>& nums) {
		int sum{};
		int count{};
		for (int num : nums) {
			if (num % 6 == 0) {
				sum += num;
				++count;
			}
		}
		return count > 0 ? sum / count : 0;
	}

	//2231. 按奇偶性交换后的最大数字
	int largestInteger(int num) {
		string str = to_string(num);
		for (int i = 0; i < str.length(); i++) {
			for (int j = i + 1; j < str.length(); j++) {
				int a = str[i] - '0';
				int b = str[j] - '0';
				if ((a % 2 == 0 && b % 2 == 0) || (a % 2 != 0 && b % 2 != 0)) {
					if (a < b)
						swap(str[i], str[j]);
				}
			}
		}
		return atoi(str.c_str());
	}

	//2535. 数组元素和与数字和的绝对差
	int differenceOfSum(vector<int>& nums) {
		int sum = accumulate(nums.begin(), nums.end(), 0);
		for (int num : nums)
			sum -= ::digitSum(num);
		return abs(sum);
	}

	//1022. 从根到叶的二进制数之和
	int dfs(TreeNode* root, int val) {
		if (root == nullptr) {
			return 0;
		}
		val = (val << 1) | root->val;
		if (root->left == nullptr && root->right == nullptr) {
			return val;
		}
		return dfs(root->left, val) + dfs(root->right, val);
	}

	int sumRootToLeaf(TreeNode* root) {
		return dfs(root, 0);
	}

	//2418. 按身高排序
	vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
		map<int, string> temp;
		for (int i = 0; i < (int)heights.size(); i++)
			temp[heights[i]] = names[i];

		vector<string> result;
		for (auto it = temp.rbegin(); it != temp.rend(); it++)
			result.emplace_back(it->second);
		return result;
	}

	//2287. 重排字符形成目标字符串
	int rearrangeCharacters(string s, string target) {
		int hashTable[26] = { 0 };
		for (char c : target)
			++hashTable[c - 'a'];

		int temp[26] = { 0 };
		for (char c : s)
			++temp[c - 'a'];

		int result{ INT_MAX };
		for (int i = 0; i < 26; i++) {
			if (hashTable[i] == 0)
				continue;
			result = std::min(temp[i] / hashTable[i], result);
			if (result == 0)
				return 0;
		}
		return result;
	}

	//1791. 找出星型图的中心节点
	int findCenter(vector<vector<int>>& edges) {
		unordered_map<int, int> temp;
		for (const auto& edge : edges) {
			if (++temp[edge[0]] > 1)
				return edge[0];
			if (++temp[edge[1]] > 1)
				return edge[1];
		}
		return -1;
	}

	//1379. 找出克隆二叉树中的相同节点
	void getTargetCopy(TreeNode* tree, int val, TreeNode*& result) {
		if (!tree || result)
			return;
		if (tree->val == val) {
			result = tree;
			return;
		}
		getTargetCopy(tree->left, val, result);
		getTargetCopy(tree->right, val, result);
	}

	TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode*& target) {
		TreeNode* result{};
		getTargetCopy(cloned, target->val, result);
		return result;
	}

	//2124. 检查是否所有 A 都在 B 之前
	bool checkString(string s) {
		char last{ '\0' };
		for (const char& c : s) {
			if (last != '\0' && last == 'b' && c == 'a')
				return false;
			last = c;
		}
		return true;
	}

	//2529. 正整数和负整数的最大计数
	int maximumCount(vector<int>& nums) {
		int size = (int)nums.size();
		if (nums[0] > 0 || nums[size - 1] < 0)
			return size;
		int temp[2] = { 0 };
		for (int num : nums) {
			if (num < 0)
				++temp[0];
			else if (num > 0)
				++temp[1];
		}
		return std::max(temp[0], temp[1]);
	}

	//面试题 05.03. 翻转数位
	int reverseBits(int num) {
		std::bitset<32> bs(num);

#pragma region
		vector<int> temp;
		stack<bool> s;
		for (int i = bs.size() - 1; i >= 0; i--) {
			bool value = bs[i];
			if (!s.empty() && s.top() != value) {
				int size = s.size();
				temp.emplace_back(s.top() ? size : -size);
				clearStack(s);
			}
			s.push(value);
		}
		if (!s.empty()) {
			int size = s.size();
			temp.emplace_back(s.top() ? size : -size);
		}
#pragma endregion

		int result{ 0 };
		for (int i = 0; i < (int)temp.size(); i++) {
			int value = temp[i];
			if (value > 0) {
				result = std::max(result, value);
				continue;
			}

			int last = i - 1 >= 0 ? temp[i - 1] : 0;
			int next = i + 1 < (int)temp.size() ? temp[i + 1] : 0;
			if (value == -1)
				result = std::max(result, last + next + 1);
			else
				result = std::max(result, std::max(last, next) + 1);
		}
		return result;
	}

	//2404. 出现最频繁的偶数元素
	int mostFrequentEven(vector<int>& nums) {
		map<int, int> temp;
		for (int num : nums) {
			if (num % 2 == 0)
				++temp[num];
		}

		int result{ -1 };
		int frequent{ -1 };
		for (auto it = temp.rbegin(); it != temp.rend(); it++) {
			int value = it->second;
			if (value >= frequent) {
				result = it->first;
				frequent = value;
			}
		}
		return result;
	}

	//2520. 统计能整除数字的位数
	int countDigits(int num) {
		int count{};
		for (const char& c : to_string(num)) {
			if (num % (c - '0') == 0)
				++count;
		}
		return count;
	}

	//2180. 统计各位数字之和为偶数的整数个数
	int countEven(int num) {
		int count{};
		for (int i = 1; i <= num; i++) {
			if (::digitSum(i) % 2 == 0)
				++count;
		}
		return count;
	}

	//2315. 统计星号
	int countAsterisks(string s) {
		std::stack<char> stack;
		int count{};
		for (const char& c : s) {
			if (c == '|') {
				if (stack.empty())
					stack.emplace(c);
				else
					clearStack(stack);
			}
			else if (c == '*' && stack.empty())
				++count;
		}
		return count;
	}

	//2399. 检查相同字母间的距离
	bool checkDistances(string s, vector<int>& distance) {
		int dis[26] = { 0 };
		for (int i = 0; i < s.length(); i++) {
			int index = s[i] - 'a';
			if (dis[index] == 0)
				dis[index] = i + 1;
			else
				dis[index] = (i + 1) - dis[index];
		}
		for (int i = 0; i < 26; i++) {
			if (dis[i] != 0 && dis[i] - 1 != distance[i])
				return false;
		}
		return true;
	}

	//2042. 检查句子中的数字是否递增
	bool areNumbersAscending(string s) {
		string token{};
		int last{};
		for (const char& c : s) {
			if (c == ' ') {
				if (token != "") {
					int value = stoi(token);
					if (value <= last)
						return false;
					last = value;
					token = "";
				}
			}
			else if (isdigit(c))
				token.push_back(c);
		}
		if (token != "" && stoi(token) <= last)
			return false;
		return true;
	}

	//2220. 转换数字的最少位翻转次数
	int minBitFlips(int start, int goal) {
		std::bitset<32> bs(start ^ goal);
		return bs.count();
	}

	//2185. 统计包含给定前缀的字符串
	int prefixCount(vector<string>& words, string pref) {
		int count{};
		size_t size{ pref.size() };
		for (const string& word : words) {
			if (word.compare(0, size, pref) == 0)
				++count;
		}
		return count;
	}

	//2325. 解密消息
	string decodeMessage(string key, string message) {
		char hashTable[26] = { '\0' };

		char a = 'a';
		for (char c : key) {
			if (c == '\0' || c == ' ')
				continue;
			if (hashTable[c - 'a'] == '\0') {
				hashTable[c - 'a'] = a;
				++a;
			}
		}

		for (char& c : message) {
			if (c == '\0' || c == ' ')
				continue;
			c = hashTable[c - 'a'];
		}
		return message;
	}

	//2027. 转换字符串的最少操作次数
	int minimumMoves(string s) {
		int result{};
		for (int i = 0; i < (int)s.size(); ) {
			char c = s[i];
			if (c == 'X') {
				++result;
				i += 3;
			}
			else
				++i;
		}
		return result;
	}

	//2500. 删除每行中的最大值
	int deleteGreatestValue(vector<vector<int>>& grid) {
		for (auto&& row : grid)
			sort(row.begin(), row.end());

		int result{};
		for (int j = 0; j < (int)grid[0].size(); j++) {
			int maxValue{};
			for (int i = 0; i < (int)grid.size(); i++)
				maxValue = max(grid[i][j], maxValue);
			result += maxValue;
		}
		return result;
	}

	//2278. 字母在字符串中的百分比
	int percentageLetter(string s, char letter) {
		int count{};
		for (char c : s) {
			if (c == letter)
				++count;
		}
		return count * 100 / s.length();
	}

	//2413. 最小偶倍数
	int smallestEvenMultiple(int n) {
		return n % 2 == 0 ? n : 2 * n;
	}

	//1805. 字符串中不同整数的数目
	string disposePreZero(const string& digit) {
		string result = "";
		for (const char& c : digit) {
			if (c == '0' && result == "")
				continue;
			else
				result.push_back(c);
		}
		return result != "" ? result : "0";
	}

	int numDifferentIntegers(string word) {
		set<string> digits;
		string digit = "";
		for (const char& c : word) {
			if (isdigit(c))
				digit.push_back(c);
			else if (digit != "") {
				digits.emplace(disposePreZero(digit));
				digit = "";
			}
		}
		if (digit != "")
			digits.emplace(disposePreZero(digit));
		return digits.size();
	}

	//2469. 温度转换
	vector<double> convertTemperature(double celsius) {
		return { celsius + 273.15, celsius * 1.80 + 32.00 };
	}

	//1779. 找到最近的有相同 X 或 Y 坐标的点
	int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
		int distance{ INT_MAX };
		int result{ -1 };
		for (int i = (int)points.size() - 1; i >= 0; i--) {
			vector<int> point = points[i];
			if (point[0] != x && point[1] != y)
				continue;
			int dis = abs(point[0] - x) + abs(point[1] - y);
			if (dis <= distance) {
				distance = dis;
				result = i;
			}
		}
		return result;
	}

	//1662. 检查两个字符串数组是否相等
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		74.63 %
		的用户
		内存消耗：
		11.2 MB
		, 在所有 C++ 提交中击败了
		48.76 %
		的用户*/
	bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
		string str1 = "";
		for (string str : word1)
			str1 += str;

		string str2 = "";
		for (string str : word2)
			str2 += str;

		return str1 == str2;
	}

	//2357. 使数组中所有元素都等于零
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		7.9 MB
		, 在所有 C++ 提交中击败了
		82.93 %
		的用户*/
	int minimumOperations1(vector<int>& nums) {
		bool hashTable[100] = { false };
		int result{};
		for (int num : nums) {
			if (num > 0 && !hashTable[num - 1]) {
				hashTable[num - 1] = true;
				++result;
			}
		}
		return result;
	}

	//1822. 数组元素积的符号
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		86.76 %
		的用户
		内存消耗：
		10 MB
		, 在所有 C++ 提交中击败了
		26.57 %
		的用户*/
		/*int arraySign(vector<int>& nums) {
			int result{ 1 };
			for (int num : nums)
			{
				if (num < 0)
					result *= -1;
				else if (num == 0)
					return 0;
			}
			return result;
		}*/

		//2148. 元素计数
		/*执行用时：
			4 ms
			, 在所有 C++ 提交中击败了
			66.88 %
			的用户
			内存消耗：
			9 MB
			, 在所有 C++ 提交中击败了
			8.83 %
			的用户*/
			/*int countElements(vector<int>& nums) {
				sort(nums.begin(), nums.end());

				int size{ (int)nums.size() };
				int left{ 0 };
				int right{ size - 1 };

				while (left < right && nums[left] == nums[left + 1])
					++left;
				while (left < right && nums[right] == nums[right - 1])
					--right;

				int result{ right - left - 1 };
				return std::max(result, 0);
			}*/

			//2089. 找出数组排序后的目标下标
			/*执行用时：
				4 ms
				, 在所有 C++ 提交中击败了
				83.26 %
				的用户
				内存消耗：
				11.2 MB
				, 在所有 C++ 提交中击败了
				87.34 %
				的用户*/
	vector<int> targetIndices(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());
		vector<int> result;
		for (int i = 0; i < (int)nums.size(); i++) {
			if (nums[i] == target)
				result.emplace_back(i);
			else if (!result.empty())
				break;
		}
		return result;
	}

	//915. 分割数组
	int partitionDisjoint(vector<int>& nums) {
		int result{ 1 };
		int left{ nums[0] };
		int right = *min_element(nums.begin() + 1, nums.end());
		while (left > right) {
			++result;
			left = std::max(left, nums[result - 1]);
			right = *min_element(nums.begin() + result, nums.end());
		}
		return result;
	}

	//2319. 判断矩阵是否是一个 X 矩阵
	/*执行用时：
		24 ms
		, 在所有 C++ 提交中击败了
		94.22 %
		的用户
		内存消耗：
		15.8 MB
		, 在所有 C++ 提交中击败了
		86.16 %
		的用户*/
	bool checkXMatrix(vector<vector<int>>& grid) {
		int n{ (int)grid.size() };
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j || n - 1 - i == j) {
					if (grid[i][j] == 0)
						return false;
				}
				else {
					if (grid[i][j] != 0)
						return false;
				}
			}
		}
		return true;
	}

	//1784. 检查二进制字符串字段
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		33.29 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		67.35 %
		的用户*/
	bool checkOnesSegment(string s) {
		bool flag{ false };
		for (int i = s.length() - 1; i >= 0; i--) {
			if (s[i] == '1')
				flag = true;
			else {
				if (flag)
					return false;
			}
		}
		return true;
	}

	//1800. 最大升序子数组和
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		41.52 %
		的用户
		内存消耗：
		8.1 MB
		, 在所有 C++ 提交中击败了
		76.50 %
		的用户*/
	int maxAscendingSum(vector<int>& nums) {
		int result{};
		int sum{ nums[0] };
		for (int i = 1; i < (int)nums.size(); i++) {
			if (nums[i] > nums[i - 1]) {
				sum += nums[i];
			}
			else {
				result = std::max(sum, result);
				sum = nums[i];
			}
		}
		result = std::max(sum, result);
		return result;
	}

	//2068. 检查两个字符串是否几乎相等
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.1 MB
		, 在所有 C++ 提交中击败了
		76.13 %
		的用户*/
	bool checkAlmostEquivalent(string word1, string word2) {
		int hashTable1[26] = { 0 };
		int hashTable2[26] = { 0 };

		for (auto c : word1)
			++hashTable1[c - 'a'];
		for (auto c : word2)
			++hashTable2[c - 'a'];

		for (int i = 0; i < 26; i++) {
			if (abs(hashTable1[i] - hashTable2[i]) > 3)
				return false;
		}
		return true;
	}

	//2283. 判断一个数的数字计数是否等于数位的值
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.7 MB
		, 在所有 C++ 提交中击败了
		94.06 %
		的用户*/
	bool digitCount(string num) {
		int hashTable[10] = { 0 };
		for (char c : num)
			++hashTable[c - '0'];
		for (int i = 0; i < (int)num.size(); i++) {
			if (hashTable[i] != (num[i] - '0'))
				return false;
		}
		return true;
	}

	//1450. 在既定时间做作业的学生人数
	/*执行用时：8 ms, 在所有 C++ 提交中击败了54.33 % 的用户
		内存消耗：10.5 MB, 在所有 C++ 提交中击败了87.00 % 的用户*/
	int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
		int result{};
		for (int i = 0; i < (int)startTime.size(); i++) {
			if (queryTime >= startTime[i] && queryTime <= endTime[i])
				++result;
		}
		return result;
	}

	//141. 环形链表
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		35.83 %
		的用户
		内存消耗：
		10.2 MB
		, 在所有 C++ 提交中击败了
		19.11 %
		的用户*/
	bool hasCycle(ListNode* head) {
		unordered_set<ListNode*> hashTable;
		while (head) {
			if (hashTable.find(head) != hashTable.end())
				return true;
			hashTable.emplace(head);
			head = head->next;
		}
		return false;
	}

	//20. 有效的括号
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.1 MB
		, 在所有 C++ 提交中击败了
		70.81 %
		的用户*/
	bool isMatch(char& c1, char& c2) {
		return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') || (c1 == '[' && c2 == ']');
	}

	bool isValid(string s) {
		std::stack<char> ss;
		for (auto& c : s) {
			if (c == '\0')
				break;
			if (!ss.empty() && isMatch(ss.top(), c))
				ss.pop();
			else
				ss.push(c);
		}
		return ss.empty();
	}

	//145. 二叉树的后序遍历
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		40.25 %
		的用户
		内存消耗：
		8.1 MB
		, 在所有 C++ 提交中击败了
		61.99 %
		的用户*/
	void postorderTraversal(TreeNode* root, vector<int>& result) {
		if (!root)
			return;
		postorderTraversal(root->left, result);
		postorderTraversal(root->right, result);
		result.emplace_back(root->val);
	}

	vector<int> postorderTraversal(TreeNode* root) {
		vector<int> result;
		postorderTraversal(root, result);
		return result;
	}

	//94. 二叉树的中序遍历
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		8 MB
		, 在所有 C++ 提交中击败了
		92.14 %
		的用户*/
	void inorderTraversal(TreeNode* root, vector<int>& result) {
		if (!root)
			return;
		inorderTraversal(root->left, result);
		result.emplace_back(root->val);
		inorderTraversal(root->right, result);
	}

	vector<int> inorderTraversal(TreeNode* root) {
		vector<int> result;
		inorderTraversal(root, result);
		return result;
	}

	//144. 二叉树的前序遍历
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		8.3 MB
		, 在所有 C++ 提交中击败了
		13.09 %
		的用户*/
	void preorderTraversal(TreeNode* root, vector<int>& result) {
		if (!root)
			return;
		result.emplace_back(root->val);
		preorderTraversal(root->left, result);
		preorderTraversal(root->right, result);
	}

	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> result;
		preorderTraversal(root, result);
		return result;
	}

	//1413. 逐步求和得到正数的最小值
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		7.3 MB
		, 在所有 C++ 提交中击败了
		11.39 %
		的用户*/
	int minStartValue(vector<int>& nums) {
		int result{ nums[0] };
		for (int i = 1; i < (int)nums.size(); i++) {
			nums[i] += nums[i - 1];
			result = std::min(nums[i], result);
		}
		return std::max(1 - result, 1);
	}

	//1408. 数组中的字符串匹配
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		81.14 %
		的用户
		内存消耗：
		8.1 MB
		, 在所有 C++ 提交中击败了
		49.12 %
		的用户*/
	vector<string> stringMatching(vector<string>& words) {
		vector<string> result;
		for (int i = 0; i < (int)words.size(); i++) {
			string word = words[i];
			for (int j = 0; j < (int)words.size(); j++) {
				if (j != i && words[j].find(word) != string::npos) {
					result.emplace_back(word);
					break;
				}
			}
		}
		return result;
	}

	//242. 有效的字母异位词
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		9.85 %
		的用户
		内存消耗：
		7.1 MB
		, 在所有 C++ 提交中击败了
		57.74 %
		的用户*/
	bool isAnagram(string s, string t) {
		sort(s.begin(), s.end());
		sort(t.begin(), t.end());
		return s == t;
	}

	//1403. 非递增顺序的最小子序列
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		90.17 %
		的用户
		内存消耗：
		10.3 MB
		, 在所有 C++ 提交中击败了
		71.19 %
		的用户*/
	vector<int> minSubsequence(vector<int>& nums) {
		sort(nums.begin(), nums.end(), std::greater<int>());

		int total = accumulate(nums.begin(), nums.end(), 0);

		int sum{ 0 };
		for (int i = 0; i < (int)nums.size(); i++) {
			sum += nums[i];
			if (sum > total - sum)
				return vector<int>(nums.begin(), nums.begin() + i + 1);
		}
		return {};
	}

	//2351. 第一个出现两次的字母
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.1 MB
		, 在所有 C++ 提交中击败了
		6.72 %
		的用户*/
	char repeatedCharacter(string s) {
		bool hashTable[26] = { false };
		for (char c : s) {
			int index = c - 'a';
			if (hashTable[index])
				return c;
			hashTable[index] = true;
		}
		return '\0';
	}

	//2235. 两整数相加
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		54.54 %
		的用户*/
		/*int sum(int num1, int num2) {
			return num1 + num2;
		}*/

		//2236. 判断根结点是否等于子结点之和
		/*执行用时：
			4 ms
			, 在所有 C++ 提交中击败了
			49.29 %
			的用户
			内存消耗：
			12.2 MB
			, 在所有 C++ 提交中击败了
			47.04 %
			的用户*/
	bool checkTree(TreeNode* root) {
		return root->val == root->left->val + root->right->val;
	}

	//1539. 第 k 个缺失的正整数
	int getLostNum(vector<int>& arr, int i) {
		return (arr[i] - 1) - i; //缺失的元素数量
	}

	int findKthPositive(vector<int>& arr, int k) {
		if (k < arr[0])
			return k;
		int size = (int)arr.size();
		for (int i = 0; i < size; i++) {
			int n = getLostNum(arr, i);
			if (n >= k)
				return arr[i - 1] + (k - getLostNum(arr, i - 1));
		}
		return arr[size - 1] + (k - getLostNum(arr, size - 1));
	}

	//34. 在排序数组中查找元素的第一个和最后一个位置
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		92.63 %
		的用户
		内存消耗：
		13.1 MB
		, 在所有 C++ 提交中击败了
		91.96 %
		的用户*/
	vector<int> searchRange(vector<int>& nums, int target) {
		auto p = std::equal_range(nums.begin(), nums.end(), target);
		int first = distance(nums.begin(), p.first);
		if (!(first >= 0 && first < (int)nums.size() && nums[first] == target))
			first = -1;
		int last = distance(nums.begin(), p.second) - 1;
		if (!(last >= 0 && last < (int)nums.size() && nums[last] == target))
			last = -1;
		return { first, last };
	}

	//278. 第一个错误的版本
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		16.49 %
		的用户*/
	bool isBadVersion(int version) {
		return version == 4;
	}

	int firstBadVersion(int n) {
		int left = 1; int right = n;
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			bool isBad = isBadVersion(mid);
			if (!isBad)
				left = mid + 1;
			else if (isBad && mid - 1 >= 0 && !isBadVersion(mid - 1))
				return mid;
			else
				right = mid - 1;
		}
		return -1;
	}

	//744. 寻找比目标字母大的最小字母
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		77.65 %
		的用户
		内存消耗：
		15.4 MB
		, 在所有 C++ 提交中击败了
		73.35 %
		的用户*/
	char nextGreatestLetter(vector<char>& letters, char target) {
		return target < letters.back() ? *upper_bound(letters.begin(), letters.end() - 1, target) : letters[0];
	}

	//2331. 计算布尔二叉树的值
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		76.61 %
		的用户
		内存消耗：
		14.7 MB
		, 在所有 C++ 提交中击败了
		5.89 %
		的用户*/
	bool evaluateTree(TreeNode* root) {
		if (!root)
			return false;
		if (root->left && root->right) {
			if (root->val == 2)
				return evaluateTree(root->left) || evaluateTree(root->right);
			else
				return evaluateTree(root->left) && evaluateTree(root->right);
		}
		else
			return root->val == 1 ? true : false;
	}

	//1385. 两个数组间的距离值
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		84.28 %
		的用户
		内存消耗：
		12.6 MB
		, 在所有 C++ 提交中击败了
		92.46 %
		的用户*/
	int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
		sort(arr2.begin(), arr2.end());

		int cnt = 0;
		for (auto& x : arr1) {
			unsigned p = lower_bound(arr2.begin(), arr2.end(), x) - arr2.begin();
			bool ok = true;
			if (p < arr2.size()) {
				ok &= (arr2[p] - x > d);
			}
			if (p - 1 >= 0 && p - 1 <= arr2.size()) {
				ok &= (x - arr2[p - 1] > d);
			}
			cnt += ok;
		}
		return cnt;
	}

	//1260. 二维网格迁移
	/*执行用时：
		52 ms
		, 在所有 C++ 提交中击败了
		16.96 %
		的用户
		内存消耗：
		13.4 MB
		, 在所有 C++ 提交中击败了
		98.50 %
		的用户*/
		//	vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
		//		int m{ (int)grid.size() };
		//		int n{ (int)grid[0].size() };
		//
		//		for (int i = 0; i < k ; i++)
		//		{
		//			//位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
		//			//位于 grid[i][n  - 1] 的元素将会移动到 grid[i + 1][0]。
		//#pragma region
		//			for (int x = 0; x < m; x++)
		//			{
		//				for (int y = n - 1; y >= 1; y--)
		//					swap(grid[x][y - 1], grid[x][y]);
		//			}
		//#pragma endregion
		//
		//			//位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
		//#pragma region
		//			for (int x = m - 1; x >= 1; x--)
		//				swap(grid[x-1][0], grid[x][0]);
		//#pragma endregion
		//		}
		//		return grid;
		//	}

			/*执行用时：
				12 ms
				, 在所有 C++ 提交中击败了
				99.75 %
				的用户
				内存消耗：
				15.8 MB
				, 在所有 C++ 提交中击败了
				8.72 %
				的用户*/
	vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
		auto vec = matrixToVector(grid);
		int size = (int)vec.size();
		k = k % size;
		rotate(vec, size - k);
		return vectorToMatrix(vec, int(grid.size()));
	}

	//35. 搜索插入位置
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		71.86 %
		的用户
		内存消耗：
		9.4 MB
		, 在所有 C++ 提交中击败了
		37.87 %
		的用户*/
		/*int searchInsert(vector<int>& nums, int target) {
			int left{ 0 };
			int right{ (int)nums.size() - 1 };
			while (left <= right)
			{
				int mid = left + (right - left) / 2;
				int value = nums[mid];
				if (value < target)
					left = mid + 1;
				else if (value > target)
					right = mid - 1;
				else
					return mid;
			}
			return left;
		}*/

		//374. 猜数字大小
		/*执行用时：
			0 ms
			, 在所有 C++ 提交中击败了
			100.00 %
			的用户
			内存消耗：
			5.9 MB
			, 在所有 C++ 提交中击败了
			23.46 %
			的用户*/

			/**
			 * Forward declaration of guess API.
			 * @param  num   your guess
			 * @return 	     -1 if num is lower than the guess number
			 *			      1 if num is higher than the guess number
			 *               otherwise return 0
			 * int guess(int num);
			 */

	int guess(int num) {
		int pick = 6;
		if (num < pick)
			return 1;
		else if (num > pick)
			return -1;
		else
			return 0;
	}

	int guessNumber(int n) {
		int left = 1;
		int right = n;
		while (left <= right) {
			int pick = left + int((right - left) * 0.5);
			int result = guess(pick);
			if (result == 1)
				left = pick + 1;
			else if (result == -1)
				right = pick - 1;
			else
				return pick;
		}
		return 0;
	}

	//1089. 复写零
	/*执行用时：28 ms, 在所有 C++ 提交中击败了34.14 % 的用户
		内存消耗：9.4 MB, 在所有 C++ 提交中击败了54.75 % 的用户*/
	void duplicateZeros(vector<int>& arr) {
		int size = (int)arr.size();
		for (auto it = arr.begin(); it != arr.end(); ++it) {
			if (*it == 0) {
				it = arr.emplace(it, 0);
				++it;
			}
		}
		arr.erase(arr.begin() + size, arr.end());
	}

	//606. 根据二叉树创建字符串
	/*执行用时：16 ms, 在所有 C++ 提交中击败了76.29 % 的用户
		内存消耗：25.3 MB, 在所有 C++ 提交中击败了49.34 % 的用户*/
	string tree2str(TreeNode* root) {
		if (root == nullptr) {
			return "";
		}
		if (root->left == nullptr && root->right == nullptr) {
			return to_string(root->val);
		}
		if (root->right == nullptr) {
			return to_string(root->val) + "(" + tree2str(root->left) + ")";
		}
		return to_string(root->val) + "(" + tree2str(root->left) + ")(" + tree2str(root->right) + ")";
	}

	//1051. 高度检查器
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		7.8 MB
		, 在所有 C++ 提交中击败了
		95.71 %
		的用户*/
	int heightChecker(vector<int>& heights) {
		vector<int> temp{ heights };
		sort(temp.begin(), temp.end());

		int result{};
		for (int i = 0; i < (int)temp.size(); ++i) {
			if (temp[i] != heights[i])
				++result;
		}
		return result;
	}

	//589. N 叉树的前序遍历
	/*执行用时：8 ms, 在所有 C++ 提交中击败了99.72 % 的用户
		内存消耗：11.2 MB, 在所有 C++ 提交中击败了48.26 % 的用户*/
	void preorder(Node* root, vector<int>& result) {
		if (!root)
			return;
		result.emplace_back(root->val);
		for (int i = 0; i < (int)root->children.size(); i++)
			preorder(root->children[i], result);
	}

	vector<int> preorder(Node* root) {
		vector<int> result;
		preorder(root, result);
		return result;
	}

	//LCS 02. 完成一半题目
	/*执行用时：44 ms, 在所有 C++ 提交中击败了88.94% 的用户
	内存消耗：47 MB, 在所有 C++ 提交中击败了11.06% 的用户*/
	int halfQuestions(vector<int>& questions) {
		unordered_map<int, int> hashTable;
		for (int question : questions)
			++hashTable[question];

		vector<int> temp(hashTable.size());
		for (const auto& p : hashTable)
			temp.emplace_back(p.second);

		sort(temp.begin(), temp.end(), greater<int>());

		int result{};
		int half{ (int)questions.size() >> 1 };
		for (int i = 0; i < (int)temp.size(); i++) {
			++result;
			half -= temp[i];
			if (half <= 0)
				break;
		}
		return result;
	}

	//面试题 02.01. 移除重复节点
	/*执行用时：20 ms, 在所有 C++ 提交中击败了97.47 % 的用户
		内存消耗：16 MB, 在所有 C++ 提交中击败了59.24 % 的用户*/
	ListNode* removeDuplicateNodes(ListNode* head) {
		unordered_set<int> hashTable;

		ListNode* result{ head };
		ListNode* last{ head };
		ListNode* next{ head };
		while (head) {
			next = head->next;
			if (hashTable.find(head->val) != hashTable.end())
				last->next = next;
			else {
				hashTable.emplace(head->val);
				last = head;
			}
			head = next;
		}
		return result;
	}

	//剑指 Offer II 001. 整数除法
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00 % 的用户
		内存消耗：5.7 MB, 在所有 C++ 提交中击败了91.74 % 的用户*/
	int divide(int a, int b) {
		auto result = (long)a / b;
		if (result > INT_MAX || result < INT_MIN)
			return INT_MAX;
		return result;
	}

	//504. 七进制数
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.7 MB
		, 在所有 C++ 提交中击败了
		97.54 %
		的用户*/
	string convertToBase7(int num) {
		string flag = (num >= 0 ? "" : "-");

		string s = "";
		do {
			int n = abs(num % 7);
			s += to_string(n);
			num /= 7;
		} while (num);

		reverse(s.begin(), s.end());
		s = flag + s;
		return s;
	}

	//258. 各位相加
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.7 MB
		, 在所有 C++ 提交中击败了
		92.67 %
		的用户*/
	int addDigits(int num) {
		string str = to_string(num);

		int sum{};
		for (int i = 0; i < (int)str.length(); i++)
			sum += str[i] - '0';

		if (sum < 10)
			return sum;
		else
			return addDigits(sum);
	}

	//2160. 拆分数位后四位数字的最小和
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		26.37 %
		的用户*/
	int minimumSum(int num) {
		vector<int> temp;
		for (int i = 0; i < 4; i++) {
			temp.emplace_back(num % 10);
			num /= 10;
		}
		sort(temp.begin(), temp.end());
		return (temp[0] * 10 + temp[2]) + (temp[1] * 10 + temp[3]);
	}

	//剑指 Offer II 075. 数组相对排序
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		7.6 MB
		, 在所有 C++ 提交中击败了
		23.64 %
		的用户*/
	vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
		unordered_map<int, int> hashTable;
		int size = (int)arr2.size();
		for (int i = 0; i < size; i++)
			hashTable[arr2[i]] = size - i;

		sort(arr1.begin(), arr1.end(), [&](int a, int b) {
			int priorityA = hashTable[a];
			int priorityB = hashTable[b];
			if (priorityA == priorityB)
				return a < b;
			else
				return priorityA > priorityB;
			});
		return arr1;
	}

	//1189. “气球” 的最大数量
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.4 MB
		, 在所有 C++ 提交中击败了
		81.60 %
		的用户*/
	int maxNumberOfBalloons(string text) {
		int hashTable[26] = { 0 };
		for (const char& c : text)
			++hashTable[c - 'a'];

		int count{ INT_MAX };
		for (char c : "ban") {
			if (c == '\0') break;
			count = std::min(count, hashTable[c - 'a']);
		}
		for (char c : "lo") {
			if (c == '\0') break;
			count = std::min(count, hashTable[c - 'a'] / 2);
		}
		return count;
	}

	//198. 打家劫舍
	int rob(vector<int>& nums) {
		int n = nums.size();
		if (n == 0) return 0;
		if (n == 1) return nums[0];

		int dp0{ 0 };
		int dp1{ nums[0] };
		int result{ 0 };
		for (int i = 1; i < n; i++) {
			result = std::max(dp0 + nums[i], dp1);
			dp0 = dp1;
			dp1 = result;
		}
		return result;
	}

	//剑指 Offer II 018. 有效的回文
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		87.81 %
		的用户
		内存消耗：
		7.8 MB
		, 在所有 C++ 提交中击败了
		5.03 %
		的用户*/
	bool isPalindrome(string s) {
		string s1;
		for (const auto& c : s) {
			if (isdigit(c))
				s1.push_back(c);
			else if (isalpha(c))
				s1.push_back((char)tolower(c));
		}

		string s2 = s1;
		reverse(s2.begin(), s2.end());
		return s1 == s2;
	}

	//剑指 Offer II 006. 排序数组中两个数字之和
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		84.55 %
		的用户
		内存消耗：
		9.3 MB
		, 在所有 C++ 提交中击败了
		69.31 %
		的用户*/
	vector<int> twoSum(vector<int>& numbers, int target) {
		for (int i = 0; i < (int)numbers.size() - 1; i++) {
			int value = target - numbers[i];
			int j = binarySearch(numbers.begin() + i + 1, numbers.end(), value);
			if (j != -1)
				return { i, i + 1 + j };
		}
		return { -1, -1 };
	}

	//剑指 Offer II 072. 求平方根
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		38.23 %
		的用户*/
	int mySqrt(int x) {
		int left{ 0 };
		int right{ x };
		while (left <= right) {
			int mid = left + (right - left) / 2;
			auto sqr = (long)mid * mid;
			if (sqr < x)
				left = mid + 1;
			else if (sqr > x)
				right = mid - 1;
			else
				return mid;
		}
		return right;
	}

	//剑指 Offer II 024. 反转链表
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		93.74 %
		的用户
		内存消耗：
		8.1 MB
		, 在所有 C++ 提交中击败了
		37.60 %
		的用户*/
	ListNode* reverseList(ListNode* head) {
		ListNode* prev{};
		while (head) {
			ListNode* next = head->next;
			head->next = prev;
			prev = head;
			head = next;
		}
		return prev;
	}

	//剑指 Offer II 012. 左右两边子数组的和相等
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		96.98 %
		的用户
		内存消耗：
		30.3 MB
		, 在所有 C++ 提交中击败了
		36.23 %
		的用户*/
	int pivotIndex(vector<int>& nums) {
		int sum = accumulate(nums.begin(), nums.end(), 0);

		int left{ 0 };
		for (int i = 0; i < (int)nums.size(); i++) {
			if (left == sum - left - nums[i])
				return i;
			left += nums[i];
		}
		return -1;
	}

	//面试题 04.04. 检查平衡性
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		98.70 %
		的用户
		内存消耗：
		20.2 MB
		, 在所有 C++ 提交中击败了
		91.50 %
		的用户*/
	bool isBalanced(TreeNode* root) {
		if (!root)
			return true;
		return abs(getTreeHeight(root->left) - getTreeHeight(root->right)) <= 1
			&& isBalanced(root->left) && isBalanced(root->right);
	}

	//剑指 Offer 40. 最小的k个数
	/*执行用时：
		24 ms
		, 在所有 C++ 提交中击败了
		79.98 %
		的用户
		内存消耗：
		18.3 MB
		, 在所有 C++ 提交中击败了
		75.14 %
		的用户*/
	vector<int> getLeastNumbers(vector<int>& arr, int k) {
		sort(arr.begin(), arr.end());
		arr.erase(arr.begin() + k, arr.end());
		return arr;
	}

	//1725. 可以形成最大正方形的矩形数目
	/*执行用时：
		32 ms
		, 在所有 C++ 提交中击败了
		93.12 %
		的用户
		内存消耗：
		17.9 MB
		, 在所有 C++ 提交中击败了
		68.81 %
		的用户*/
		/*int countGoodRectangles(vector<vector<int>>& rectangles) {
			map<int, int> hashTable;
			for (const auto& rectangle : rectangles)
				++hashTable[std::min(rectangle[0], rectangle[1])];
			return (hashTable.rbegin())->second;
		}*/

		//2000. 反转单词前缀
		/*执行用时：
			0 ms
			, 在所有 C++ 提交中击败了
			100.00 %
			的用户
			内存消耗：
			6.1 MB
			, 在所有 C++ 提交中击败了
			52.23 %
			的用户*/
	string reversePrefix(string word, char ch) {
		for (auto it = word.begin(); it != word.end(); ++it) {
			if (*it == ch) {
				reverse(word.begin(), it + 1);
				break;
			}
		}
		return word;
	}

	//1967. 作为子字符串出现在单词中的字符串数目
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		92.97 %
		的用户
		内存消耗：
		8.5 MB
		, 在所有 C++ 提交中击败了
		66.02 %
		的用户*/
	int numOfStrings(vector<string>& patterns, string word) {
		int count{};
		for (const auto& pattern : patterns) {
			if (word.find(pattern) != string::npos)
				++count;
		}
		return count;
	}

	//剑指 Offer 58 - I. 翻转单词顺序
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		82.56 %
		的用户
		内存消耗：
		9.1 MB
		, 在所有 C++ 提交中击败了
		21.09 %
		的用户*/
	string reverseWords(string s) {
		auto&& words = stringToWordVector(s);

		string result;
		for (int i = words.size() - 1; i >= 0; i--)
			result += words[i] + " ";
		return result.substr(0, result.length() - 1);
	}

	//1991. 找到数组的中间位置
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		12.1 MB
		, 在所有 C++ 提交中击败了
		21.02 %
		的用户*/
	int findMiddleIndex(vector<int>& nums) {
		int sum = accumulate(nums.begin(), nums.end(), 0);

		int left{ 0 };
		for (int i = 0; i < (int)nums.size(); i++) {
			if (i - 1 >= 0)
				left += nums[i - 1];
			if (left == sum - left - nums[i])
				return i;
		}
		return -1;
	}

	//1984. 学生分数的最小差值
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		87.38 %
		的用户
		内存消耗：
		13.3 MB
		, 在所有 C++ 提交中击败了
		38.79 %
		的用户*/
	int minimumDifference(vector<int>& nums, int k) {
		if (k == 1)
			return 0;
		sort(nums.begin(), nums.end());
		int result{ INT_MAX };
		for (int i = 0; i < (int)nums.size() - (k - 1); i++)
			result = std::min(nums[i + k - 1] - nums[i], result);
		return result;
	}

	//884. 两句话中的不常见单词
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.5 MB
		, 在所有 C++ 提交中击败了
		76.92 %
		的用户*/
	vector<string> uncommonFromSentences(string s1, string s2) {
		auto&& map1 = stringToWordHashMap(s1);
		auto&& map2 = stringToWordHashMap(s2);

		vector<string> result;
		for (const auto& p : map1) {
			if (p.second == 1 && map2.find(p.first) == map2.end())
				result.emplace_back(p.first);
		}
		for (const auto& p : map2) {
			if (p.second == 1 && map1.find(p.first) == map1.end())
				result.emplace_back(p.first);
		}
		return result;
	}

	//LCS 01. 下载插件
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		80.37 %
		的用户*/
	int leastMinutes(int n) {
		if (n < 4)
			return n;

		int temp{ 1 };
		int result{ 0 };
		while (temp < n) {
			temp <<= 1;
			++result;
		}
		return result + 1;
	}

	//2114. 句子中的最多单词数
	/*执行用时：8 ms, 在所有 C++ 提交中击败了92.63 % 的用户
		内存消耗：9.4 MB, 在所有 C++ 提交中击败了80.95 % 的用户*/
	int mostWordsFound(vector<string>& sentences) {
		int result{ 0 };
		for (const auto& sentence : sentences) {
			int count{ 1 };
			for (const char& c : sentence) {
				if (c == ' ')
					++count;
			}
			result = std::max(count, result);
		}
		return result;
	}

	//228. 汇总区间
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.6 MB
		, 在所有 C++ 提交中击败了
		76.41 %
		的用户*/
	vector<string> summaryRanges(vector<int>& nums) {
		vector<string> result;
		if (nums.empty())
			return result;

		int first{ nums[0] };
		int last{ nums[0] };
		for (int i = 1; i < (int)nums.size(); i++) {
			if (nums[i] != last + 1) {
				if (first != last)
					result.emplace_back(to_string(first) + "->" + to_string(last));
				else
					result.emplace_back(to_string(first));
				first = nums[i];
			}
			last = nums[i];
		}

		if (first != last)
			result.emplace_back(to_string(first) + "->" + to_string(last));
		else
			result.emplace_back(to_string(first));

		return result;
	}

	//1185. 一周中的第几天
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		5.28 %
		的用户*/
	string dayOfTheWeek(int day, int month, int year) {
		string weekdays[]{ "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" };
		tm time{ 0, 0, 0, day, month - 1, year - 1900 };
		mktime(&time);
		return weekdays[time.tm_wday];
	}

	//1903. 字符串中的最大奇数
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		99.21 %
		的用户
		内存消耗：
		14.6 MB
		, 在所有 C++ 提交中击败了
		42.89 %
		的用户*/
	string largestOddNumber(string num) {
		for (int i = (int)num.length() - 1; i >= 0; i--) {
			if (((num[i] - '0') & 1) != 0)
				return num.substr(0, i + 1);
		}
		return "";
	}

	//2022. 将一维数组转变成二维数组
	/*执行用时：
		84 ms
		, 在所有 C++ 提交中击败了
		96.35 %
		的用户
		内存消耗：
		85.1 MB
		, 在所有 C++ 提交中击败了
		53.97 %
		的用户*/
	vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
		vector<vector<int>> result;
		if ((int)original.size() != m * n)
			return result;

		for (int i = 0; i < (int)original.size(); i += n)
			result.emplace_back(original.begin() + i, original.begin() + i + n);
		return result;
	}

	//1154. 一年中的第几天
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		82.04 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		49.38 %
		的用户*/
	int dayOfYear(string date) {
		int year = stoi(date.substr(0, 4));
		int month = stoi(date.substr(5, 2));
		int day = stoi(date.substr(8, 2));

		int amount[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
		if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
			++amount[1];
		}

		int ans = 0;
		for (int i = 0; i < month - 1; ++i) {
			ans += amount[i];
		}
		return ans + day;
	}

	//383. 赎金信
	bool canConstruct(string ransomNote, string magazine) {
		if (ransomNote.size() > magazine.size()) {
			return false;
		}
		vector<int> cnt(26);
		for (auto& c : magazine) {
			cnt[c - 'a']++;
		}
		for (auto& c : ransomNote) {
			cnt[c - 'a']--;
			if (cnt[c - 'a'] < 0) {
				return false;
			}
		}
		return true;
	}

	//1005. K 次取反后最大化的数组和
	/*执行用时：4 ms, 在所有 C++ 提交中击败了90.00 % 的用户
		内存消耗：8.8 MB, 在所有 C++ 提交中击败了58.99 % 的用户*/
	int largestSumAfterKNegations(vector<int>& nums, int k) {
		sort(nums.begin(), nums.end());
		for (int i = 0; i < (int)nums.size(); i++) {
			if (k <= 0)
				break;

			if (nums[i] < 0) {
				nums[i] = -nums[i];
				--k;
			}
		}

		if (k % 2 != 0) {
			auto it = std::min_element(nums.begin(), nums.end());
			*it = -*it;
		}
		return accumulate(nums.begin(), nums.end(), 0);
	}

	//1446. 连续字符
	/*执行用时：4 ms, 在所有 C++ 提交中击败了79.78 % 的用户
		内存消耗：6.6 MB, 在所有 C++ 提交中击败了80.87 % 的用户*/
	int maxPower(string s) {
		int result{};

		char last = ' ';
		int count{};
		for (const auto& c : s) {
			if (last == ' ' || c == last)
				++count;
			else
				count = 1;

			last = c;
			result = std::max(count, result);
		}
		return result;
	}

	//598. 范围求和 II
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		90.97 %
		的用户
		内存消耗：
		10.7 MB
		, 在所有 C++ 提交中击败了
		85.24 %
		的用户*/
	int maxCount(int m, int n, vector<vector<int>>& ops) {
		int a{ m };
		int b{ n };
		for (const auto& op : ops) {
			a = std::min(op[0], a);
			b = std::min(op[1], b);
		}
		return a * b;
	}

	//2057. 值相等的最小索引
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		82.86 %
		的用户
		内存消耗：
		21.3 MB
		, 在所有 C++ 提交中击败了
		92.85 %
		的用户*/
	int smallestEqual(vector<int>& nums) {
		for (int i = 0; i < (int)nums.size(); i++) {
			if (i % 10 == nums[i])
				return i;
		}
		return -1;
	}

	//268. 丢失的数字
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		99.30 %
		的用户
		内存消耗：
		17.5 MB
		, 在所有 C++ 提交中击败了
		80.18 %
		的用户*/
		/*int missingNumber(vector<int>& nums) {
			int size = (int)nums.size();
			return (size + 1) * size * 0.5 - accumulate(nums.begin(), nums.end(), 0);
		}*/

		//237. 删除链表中的节点
		/*执行用时：8 ms, 在所有 C++ 提交中击败了89.52 % 的用户
			内存消耗：7.5 MB, 在所有 C++ 提交中击败了53.46 % 的用户*/
	void deleteNode(ListNode* node) {
		node->val = node->next->val;
		node->next = node->next->next;
	}

	//575. 分糖果
	/*执行用时：156 ms, 在所有 C++ 提交中击败了92.10% 的用户
	内存消耗：100.1 MB, 在所有 C++ 提交中击败了72.31% 的用户*/
	int distributeCandies(vector<int>& candyType) {
		int result{ (int)candyType.size() >> 1 };

		std::unordered_set<int> setType;
		for (const auto& type : candyType) {
			if (setType.find(type) == setType.end())
				setType.emplace(type);
			if ((int)setType.size() >= result)
				break;
		}

		return std::min((int)setType.size(), result);
	}

	//367. 有效的完全平方数
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		22.84 %
		的用户*/
	bool isPerfectSquare(int num) {
		int x = (int)sqrt(num);
		return x * x == num;
	}

	//500. 键盘行
	/*执行用时：
	0 ms
	, 在所有 C++ 提交中击败了
	100.00%
	的用户
	内存消耗：
	7.1 MB
	, 在所有 C++ 提交中击败了
	5.02%
	的用户*/
	int findCharLine(char c) {
		const vector<vector<char>> keybord =
		{
			{ 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p' },
			{ 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'l' },
			{ 'z', 'x', 'c', 'v', 'b', 'n', 'm', 'm', 'm', 'm' },
		};

		for (int i = 0; i < (int)keybord.size(); i++) {
			for (int j = 0; j < (int)keybord[i].size(); j++) {
				if (tolower(c) == keybord[i][j])
					return i;
			}
		}
		return -1;
	}

	int findWordLine(string word) {
		std::unordered_set<int> temp;
		for (auto c : word)
			temp.emplace(findCharLine(c));
		return temp.size() == 1 ? *(temp.begin()) : -1;
	}

	vector<string> findWords(vector<string>& words) {
		for (auto it = words.begin(); it != words.end();) {
			if (findWordLine(*it) == -1)
				it = words.erase(it);
			else
				++it;
		}
		return words;
	}

	//453. 最小操作次数使数组元素相等
	/*执行用时：36 ms, 在所有 C++ 提交中击败了62.17 % 的用户
		内存消耗：27.4 MB, 在所有 C++ 提交中击败了100.00 % 的用户*/
	int minMoves(vector<int>& nums) {
		if (nums.size() < 2)
			return 0;

		sort(nums.begin(), nums.end());

		int count = 0;
		for (int i = (int)nums.size() - 1; i >= 0; --i)
			count += (nums[i] - nums[0]);
		return count;
	}

	//405. 数字转换为十六进制数
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00 % 的用户
		内存消耗：5.9 MB, 在所有 C++ 提交中击败了14.04 % 的用户*/
	string toHex(int num) {
		stringstream ss;
		ss << hex << num;
		return ss.str();
	}

	//476. 数字的补数
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00 % 的用户
		内存消耗：5.8 MB, 在所有 C++ 提交中击败了69.28 % 的用户*/
	int findComplement(int num) {
		std::bitset<32> bs(num);

		int pos = 0;
		for (int i = (int)bs.size() - 1; i > 0; --i) {
			if (!bs.test(i) && bs.test(i - 1)) {
				pos = i - 1;
				break;
			}
		}

		for (int i = 0; i <= pos; ++i)
			bs.flip(i);

		return bs.to_ulong();
	}

	//412. Fizz Buzz
	/*执行用时：4 ms, 在所有 C++ 提交中击败了82.41 % 的用户
		内存消耗：7.9 MB, 在所有 C++ 提交中击败了5.60 % 的用户*/
	vector<string> fizzBuzz(int n) {
		vector<string> result;
		for (int i = 1; i <= n; i++) {
			bool fizz = i % 3 == 0;
			bool buzz = i % 5 == 0;
			if (fizz && buzz)
				result.emplace_back("FizzBuzz");
			else if (fizz)
				result.emplace_back("Fizz");
			else if (buzz)
				result.emplace_back("Buzz");
			else
				result.emplace_back(to_string(i));
		}
		return result;
	}

	//414. 第三大的数
	/*执行用时：4 ms, 在所有 C++ 提交中击败了92.17 % 的用户
		内存消耗：10.4 MB, 在所有 C++ 提交中击败了11.93 % 的用户*/
	int thirdMax(vector<int>& nums) {
		set<int> temp(nums.begin(), nums.end());

		auto it = temp.rbegin();
		if (temp.size() > 2) {
			++it; ++it;
		}
		return *it;
	}

	//441. 排列硬币
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户
	内存消耗：5.8 MB, 在所有 C++ 提交中击败了86.05% 的用户*/
	int arrangeCoins(int n) {
		int left = 1, right = n;
		while (left < right) {
			int mid = (right - left + 1) / 2 + left;
			if ((long long)mid * (mid + 1) <= (long long)2 * n) {
				left = mid;
			}
			else {
				right = mid - 1;
			}
		}
		return left;
	}

	//LCP 44. 开幕式焰火
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		88.85 %
		的用户
		内存消耗：
		22.4 MB
		, 在所有 C++ 提交中击败了
		37.75 %
		的用户*/
	int numColor(TreeNode* root) {
		unordered_set<int> result;
		numColor(root, result);
		return (int)result.size();
	}

	void numColor(TreeNode* root, unordered_set<int>& result) {
		if (!root)
			return;
		result.emplace(root->val);
		numColor(root->left, result);
		numColor(root->right, result);
	}

	//2011. 执行操作后的变量值
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		94.62 %
		的用户
		内存消耗：
		13.7 MB
		, 在所有 C++ 提交中击败了
		42.18 %
		的用户*/
	int finalValueAfterOperations(vector<string>& operations) {
		int X{};
		for (const auto& operation : operations) {
			if (operation == "++X" or operation == "X++")
				++X;
			else
				--X;
		}
		return X;
	}

	//剑指 Offer 22. 链表中倒数第k个节点
	/*执行用时：4 ms, 在所有 C++ 提交中击败了72.15 % 的用户
		内存消耗：10.3 MB, 在所有 C++ 提交中击败了73.86 % 的用户*/
	ListNode* getKthFromEnd(ListNode* head, int k) {
		ListNode* first{ head };
		ListNode* second{ head };

		for (int i = 0; i < k; ++i)
			second = second->next;

		while (second) {
			first = first->next;
			second = second->next;
		}
		return first;
	}

	//1221. 分割平衡字符串
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.2 MB
		, 在所有 C++ 提交中击败了
		30.64 %
		的用户*/
	int balancedStringSplit(string s) {
		int result{};
		int num{};
		for (int i = 0; i < (int)s.length(); i++) {
			s[i] == 'L' ? ++num : --num;
			if (num == 0)
				++result;
		}
		return result;
	}

	//704. 二分查找
	/*执行用时：
		28 ms
		, 在所有 C++ 提交中击败了
		89.11 %
		的用户
		内存消耗：
		27 MB
		, 在所有 C++ 提交中击败了
		10.18 %
		的用户*/
	int search(vector<int>& nums, int target) {
		int left = 0;
		int right = (int)nums.size() - 1;
		while (left <= right) {
			const int& mid = left + int((right - left) * 0.5);
			const int& num = nums[mid];
			if (num == target)
				return mid;
			else if (num < target)
				left = mid + 1;
			else
				right = mid - 1;
		}
		return -1;
	}

	//1913. 两个数对之间的最大乘积差
	/*执行用时：
		28 ms
		, 在所有 C++ 提交中击败了
		85.64 %
		的用户
		内存消耗：
		19.8 MB
		, 在所有 C++ 提交中击败了
		93.50 %
		的用户*/
	int maxProductDifference(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int size = (int)nums.size();
		return (nums[size - 1] * nums[size - 2]) - (nums[0] * nums[1]);
	}

	//1920. 基于排列构建数组
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		98.46 %
		的用户
		内存消耗：
		15.9 MB
		, 在所有 C++ 提交中击败了
		38.57 %
		的用户*/
	vector<int> buildArray(vector<int>& nums) {
		vector<int> result;
		result.reserve(nums.size());
		for (int i = 0; i < (int)nums.size(); i++)
			result.emplace_back(nums[nums[i]]);
		return result;
	}

	//1929. 数组串联
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		95.64 %
		的用户
		内存消耗：
		12.4 MB
		, 在所有 C++ 提交中击败了
		40.37 %
		的用户*/
	vector<int> getConcatenation(vector<int>& nums) {
		nums.reserve(nums.size() * 2);
		nums.insert(nums.end(), nums.begin(), nums.end());
		return nums;
	}

	//136. 只出现一次的数字
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		96.67 %
		的用户
		内存消耗：
		16.5 MB
		, 在所有 C++ 提交中击败了
		41.87 %
		的用户*/
	int singleNumber(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		for (int i = 0; i < (int)nums.size() - 1; i += 2) {
			if (nums[i] != nums[i + 1])
				return nums[i];
		}
		return *nums.rbegin();
	}

	//387. 字符串中的第一个唯一字符
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		10.3 MB
		, 在所有 C++ 提交中击败了
		94.15 %
		的用户*/
	int firstUniqChar(string s) {
		int hashtable[26] = { 0 };
		for (int i = 0; i < (int)s.length(); i++)
			++hashtable[s[i] - 'a'];
		for (int i = 0; i < (int)s.length(); i++) {
			if (hashtable[s[i] - 'a'] == 1)
				return i;
		}
		return -1;
	}

	//73. 矩阵置零
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		88.19 %
		的用户
		内存消耗：
		13.1 MB
		, 在所有 C++ 提交中击败了
		6.97 %
		的用户*/
	void setZeroes(vector<vector<int>>& matrix) {
		int m = (int)matrix.size();
		int n = (int)matrix[0].size();

		unordered_set<int> row;
		for (int i = 0; i < m; i++) {
			auto it = std::find(matrix[i].begin(), matrix[i].end(), 0);
			if (it != matrix[i].end())
				row.emplace(i);
		}

		unordered_set<int> col;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (matrix[j][i] == 0) {
					col.emplace(i);
					break;
				}
			}
		}

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == 0)
					continue;
				if (row.find(i) != row.end() || col.find(j) != col.end())
					matrix[i][j] = 0;
			}
		}
	}

	//36. 有效的数独
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		98.63 %
		的用户
		内存消耗：
		17.4 MB
		, 在所有 C++ 提交中击败了
		93.39 %
		的用户*/
	bool isValidSudoku(vector<vector<char>>& board) {
		//check row
		for (int i = 0; i < 9; i++) {
			bool hashtable[9] = { false };
			for (int j = 0; j < 9; j++) {
				if (board[i][j] == '.') continue;
				if (hashtable[board[i][j] - '1'])
					return false;
				hashtable[board[i][j] - '1'] = true;
			}
		}

		//check col
		for (int i = 0; i < 9; i++) {
			bool hashtable[9] = { false };
			for (int j = 0; j < 9; j++) {
				if (board[j][i] == '.') continue;
				if (hashtable[board[j][i] - '1'])
					return false;
				hashtable[board[j][i] - '1'] = true;
			}
		}

		//check 3X3
		for (int i = 0; i < 9; i += 3) {
			for (int j = 0; j < 9; j += 3) {
				bool hashtable[9] = { false };
				for (int m = i; m < i + 3; m++) {
					for (int n = j; n < j + 3; n++) {
						if (board[m][n] == '.') continue;
						if (hashtable[board[m][n] - '1'])
							return false;
						hashtable[board[m][n] - '1'] = true;
					}
				}
			}
		}

		return true;
	}

	//118. 杨辉三角
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.5 MB
		, 在所有 C++ 提交中击败了
		14.46 %
		的用户*/
	vector<vector<int>> generate(int numRows) {
		vector<vector<int>> result;
		result.resize(numRows);
		result[0] = { 1 };

		for (int row = 2; row <= numRows; row++) {
			for (int col = 0; col < row; col++) {
				if (col == 0 || col == row - 1)
					result[row - 1].emplace_back(1);
				else
					result[row - 1].emplace_back(result[row - 2][col - 1] + result[row - 2][col]);
			}
		}
		return result;
	}

	//566. 重塑矩阵
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		91.90 %
		的用户
		内存消耗：
		10.5 MB
		, 在所有 C++ 提交中击败了
		29.79 %
		的用户*/
	vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
		if (mat.empty() || mat[0].empty())
			return mat;

		int row = (int)mat.size();
		int col = (int)mat[0].size();
		if (row * col != r * c)
			return mat;

		vector<vector<int>> result;
		result.resize(r);
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++)
				result[(i * col + j) / c].emplace_back(mat[i][j]);
		}
		return result;
	}

	//350. 两个数组的交集 II
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00 % 的用户
	内存消耗：9.8 MB, 在所有 C++ 提交中击败了63.37 % 的用户*/
	vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
		std::sort(nums1.begin(), nums1.end());
		std::sort(nums2.begin(), nums2.end());

		std::vector<int> v_intersection;
		std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), std::back_inserter(v_intersection));
		return v_intersection;
	}

	//88. 合并两个有序数组
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00 % 的用户
	内存消耗：8.8 MB, 在所有 C++ 提交中击败了73.45 % 的用户*/
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		vector<int> temp;
		temp.reserve(m + n);

		int i = 0, j = 0;
		while (i < m && j < n) {
			if (nums1[i] < nums2[j]) {
				temp.emplace_back(nums1[i]);
				++i;
			}
			else {
				temp.emplace_back(nums2[j]);
				++j;
			}
		}

		for (; i < m; i++)
			temp.emplace_back(nums1[i]);

		for (; j < n; j++)
			temp.emplace_back(nums2[j]);

		nums1 = std::move(temp);
	}

	//1. 两数之和
	/*执行用时：8 ms, 在所有 C++ 提交中击败了85.15 % 的用户
	内存消耗：10.5 MB, 在所有 C++ 提交中击败了30.84 % 的用户*/
	/*vector<int> twoSum(vector<int>& nums, int target) {
		unordered_map<int, int> hashtable;
		for (int i = 0; i < (int)nums.size(); ++i) {
			auto it = hashtable.find(target - nums[i]);
			if (it != hashtable.end()) {
				return { it->second, i };
			}
			hashtable[nums[i]] = i;
		}
		return {};
	}*/

	//53. 最大子序和
	/*执行用时：4 ms, 在所有 C++ 提交中击败了95.21 % 的用户
		内存消耗：12.7 MB, 在所有 C++ 提交中击败了89.34 % 的用户*/
	int maxSubArray(vector<int>& nums) {
		for (int i = 1; i < (int)nums.size(); i++)
			nums[i] = max(nums[i - 1] + nums[i], nums[i]);
		return *max_element(nums.begin(), nums.end());
	}

	//1846. 减小和重新排列数组后的最大元素
	/*执行用时：
		88 ms
		, 在所有 C++ 提交中击败了
		98.68 %
		的用户
		内存消耗：
		50.1 MB
		, 在所有 C++ 提交中击败了
		52.48 %
		的用户*/
	int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
		sort(arr.begin(), arr.end());
		arr[0] = 1;
		for (int i = 1; i < (int)arr.size() - 1; i++) {
			if (arr[i + 1] > arr[i])
				arr[i + 1] = arr[i] + 1;
		}
		return std::min(*arr.rbegin(), (int)arr.size());
	}

	//1331. 数组序号转换
	/*执行用时：
		132 ms
		, 在所有 C++ 提交中击败了
		74.58 %
		的用户
		内存消耗：
		46.9 MB
		, 在所有 C++ 提交中击败了
		20.67 %
		的用户*/
	vector<int> arrayRankTransform(vector<int>& arr) {
		std::map<int, vector<int>> temp;
		for (int i = 0; i < (int)arr.size(); ++i)
			temp[arr[i]].emplace_back(i);

		int index{ 1 };
		for (const auto& p : temp) {
			for (const auto& n : p.second)
				arr[n] = index;
			++index;
		}
		return arr;
	}

	//1646. 获取生成数组中的最大值
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.1 MB
		, 在所有 C++ 提交中击败了
		51.00 %
		的用户*/
	int getMaximumGenerated(int n) {
		if (n < 2)
			return n;

		vector<int> result{ 0, 1 };
		for (int i = 2; i <= n; i++) {
			int value = (i % 2 == 0) ? result[i / 2] : (result[(i - 1) / 2] + result[(i - 1) / 2 + 1]);
			result.emplace_back(value);
		}
		return *max_element(result.begin(), result.end());
	}

	//LCP 07. 传递信息
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		70.68 %
		的用户
		内存消耗：
		7 MB
		, 在所有 C++ 提交中击败了
		37.46 %
		的用户*/
	int numWays(int n, vector<vector<int>>& relation, int k) {
		vector<vector<int>> edges(n);
		for (auto& edge : relation) {
			int src = edge[0], dst = edge[1];
			edges[src].push_back(dst);
		}

		int ways = 0;
		function<void(int, int)> dfs = [&](int index, int steps) {
			if (steps == k) {
				if (index == n - 1) {
					++ways;
				}
				return;
			}
			for (int to : edges[index]) {
				dfs(to, steps + 1);
			}
		};
		dfs(0, 0);
		return ways;
	}

	//面试题 17.10. 主要元素
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		91.20 %
		的用户
		内存消耗：
		18.4 MB
		, 在所有 C++ 提交中击败了
		17.51 %
		的用户*/
	int majorityElement(vector<int>& nums) {
		std::unordered_map<int, int> temp;
		int half{ (int)nums.size() / 2 };
		for (auto n : nums) {
			int& value = temp[n];
			++value;
			if (value > half)
				return n;
		}
		return -1;
	}

	//168. Excel表列名称
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		55.45 %
		的用户*/
	string convertToTitle(int n) {
		string result;
		while (n != 0) {
			int mod = (n - 1) % 26; //[0,25]
			n = (n - 1) / 26;
			result += (char)('A' + mod);
		}
		reverse(result.begin(), result.end());
		return result;
	}

	//401. 二进制手表
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.3 MB
		, 在所有 C++ 提交中击败了
		58.60 %
		的用户*/
	vector<string> readBinaryWatch(int turnedOn) {
		vector<string> ans;
		for (int h = 0; h < 12; ++h) {
			for (int m = 0; m < 60; ++m) {
				std::bitset<4> hour(h);
				std::bitset<6> minute(m);
				if ((int)hour.count() + (int)minute.count() == turnedOn) {
					ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
				}
			}
		}
		return ans;
	}

	//852. 山脉数组的峰顶索引
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		94.97 %
		的用户
		内存消耗：
		11.3 MB
		, 在所有 C++ 提交中击败了
		23.53 %
		的用户*/
	int peakIndexInMountainArray(vector<int>& arr) {
		int left{ 1 };
		int right{ (int)arr.size() - 2 };
		while (left <= right) {
			int middle = left + ((right - left) >> 1);
			int b = arr[middle];
			if (b <= arr[middle + 1])
				left = middle + 1;
			else if (b <= arr[middle - 1])
				right = middle - 1;
			else
				return middle;
		}
		return -1;
	}

	//1876. 长度为三且各字符不同的子字符串
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		59.53 %
		的用户*/
	int countGoodSubstrings(string s) {
		int result{};
		for (int i = 0; i < (int)s.length() - 2; i++) {
			char a = s[i];
			char b = s[i + 1];
			char c = s[i + 2];
			if (a != b && a != c && b != c)
				++result;
		}
		return result;
	}

	//1668. 最大重复子字符串
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.2 MB
		, 在所有 C++ 提交中击败了
		14.45 %
		的用户*/
	int maxRepeating(string sequence, string word) {
		int result{};
		string temp{ word };
		while (sequence.find(temp) != string::npos) {
			++result;
			temp += word;
		}
		return result;
	}

	//1629. 按键持续时间最长的键
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		99.65 %
		的用户
		内存消耗：
		10.3 MB
		, 在所有 C++ 提交中击败了
		87.02 %
		的用户*/
	char slowestKey(vector<int>& releaseTimes, string keysPressed) {
		vector<int> temp;
		temp.resize(26, 0);

		int pressTime{};
		for (int i = 0; i < (int)keysPressed.length(); i++) {
			char key = keysPressed[i];
			temp[key - 'a'] = std::max(releaseTimes[i] - pressTime, temp[key - 'a']);
			pressTime = releaseTimes[i];
		}

		auto it = max_element(temp.rbegin(), temp.rend());
		return (char)distance(temp.begin(), (++it).base()) + 'a';
	}

	//剑指 Offer 53 - I. 在排序数组中查找数字 I
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		80.67 %
		的用户
		内存消耗：
		12.8 MB
		, 在所有 C++ 提交中击败了
		72.45 %
		的用户*/
		/*int search(vector<int>& nums, int target) {
			int ret{};
			for (auto n : nums)
			{
				if (n > target)
					break;
				if (n == target)
					++ret;
			}
			return ret;
		}*/

		//523. 连续的子数组和
		/*执行用时：
			176 ms
			, 在所有 C++ 提交中击败了
			64.91 %
			的用户
			内存消耗：
			94.3 MB
			, 在所有 C++ 提交中击败了
			32.67 %
			的用户*/
	bool checkSubarraySum(vector<int>& nums, int k) {
		int size = (int)nums.size();
		if (size < 2)
			return false;

		unordered_map<int, int> remainder;

		int sum{ 0 };
		for (int i = 0; i < size; i++) {
			sum += nums[i]; //sum[0,i]
			int mod = (sum % k);
			if (i > 0 && mod == 0)
				return true;
			else if (remainder.find(mod) == remainder.end())
				remainder.insert({ mod, i });
			else if (i - remainder[mod] > 1)
				return true;
		}
		return false;
	}

	//1422. 分割字符串的最大得分
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.2 MB
		, 在所有 C++ 提交中击败了
		62.22 %
		的用户*/
	int maxScore(string s) {
		int left{};
		int right{};

		int ptr{ 1 };
		for (int i = 0; i < (int)s.length(); i++) {
			if (i < ptr && s[i] == '0')
				++left;
			if (i >= ptr && s[i] == '1')
				++right;
		}

		int score{ left + right };
		int ret{ score };
		for (int i = ptr; i < (int)s.length() - 1; i++) {
			if (s[i] == '0')
				++score;
			else
				--score;

			ret = std::max(score, ret);
		}
		return ret;
	}

	//面试题 10.05. 稀疏数组搜索
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		86.81 %
		的用户
		内存消耗：
		11.7 MB
		, 在所有 C++ 提交中击败了
		5.07 %
		的用户*/
	int findString(vector<string>& words, string s) {
		std::unordered_map<string, int> temp;
		for (int i = 0; i < (int)words.size(); i++)
			temp[words[i]] = i + 1;
		return temp[s] - 1;
	}

	//面试题 01.04. 回文排列
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.1 MB
		, 在所有 C++ 提交中击败了
		64.75 %
		的用户*/
	bool canPermutePalindrome(string s) {
		std::unordered_map<char, int> temp;
		for (auto c : s) {
			++temp[c];
		}

		int flag{};
		for (const auto& p : temp) {
			if (p.second % 2 != 0) {
				++flag;
				if (flag > 1)
					return false;
			}
		}
		return true;
	}

	//面试题 10.01. 合并排序的数组
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		8.9 MB
		, 在所有 C++ 提交中击败了
		8.37 %
		的用户*/
		/*void merge(vector<int>& A, int m, vector<int>& B, int n) {
			vector<int> temp;
			temp.reserve(m + n);

			int i = 0, j = 0;
			while (i < m && j < n)
			{
				if (A[i] < B[j])
				{
					temp.emplace_back(A[i]);
					++i;
				}
				else
				{
					temp.emplace_back(B[j]);
					++j;
				}
			}

			for (; i < m ; i++)
				temp.emplace_back(A[i]);

			for (; j < n; j++)
				temp.emplace_back(B[j]);

			A = std::move(temp);
		}*/

		//面试题 01.09. 字符串轮转
		/*执行用时：
			4 ms
			, 在所有 C++ 提交中击败了
			91.36 %
			的用户
			内存消耗：
			7.6 MB
			, 在所有 C++ 提交中击败了
			73.31 %
			的用户*/
	bool isFlipedString(string s1, string s2) {
		if (s1.length() != s2.length())
			return false;
		return (s2 + s2).find(s1) != string::npos;
	}

	//面试题 08.10. 颜色填充
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		84.22 %
		的用户
		内存消耗：
		13.2 MB
		, 在所有 C++ 提交中击败了
		44.01 %
		的用户*/
	void floodFill(vector<vector<int>>& image, int sr, int sc, int oldColor, int newColor) {
		if ((sr < 0 || sr >= (int)image.size()) || (sc < 0 || sc >= (int)image[0].size())) {
			return;
		}

		if (image[sr][sc] != oldColor || image[sr][sc] == newColor) {
			return;
		}

		image[sr][sc] = newColor;

		floodFill(image, sr, sc + 1, oldColor, newColor);
		floodFill(image, sr, sc - 1, oldColor, newColor);
		floodFill(image, sr - 1, sc, oldColor, newColor);
		floodFill(image, sr + 1, sc, oldColor, newColor);
	}

	vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
		floodFill(image, sr, sc, image[sr][sc], newColor);
		return image;
	}

	//剑指 Offer 11. 旋转数组的最小数字
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		92.24 %
		的用户
		内存消耗：
		11.8 MB
		, 在所有 C++ 提交中击败了
		22.04 %
		的用户*/
	int minArray(vector<int>& numbers) {
		for (int i = 0; i < (int)numbers.size() - 1; i++) {
			if (numbers[i] > numbers[i + 1])
				return numbers[i + 1];
		}
		return numbers[0];
	}

	//1869. 哪种连续子字符串更长
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		62.44 %
		的用户*/
	bool checkZeroOnes(string s) {
		char last{};
		int size{};

		vector<int> ret{ 0, 0 };
		for (int i = 0; i < (int)s.size(); i++) {
			if (last != '\0' && s[i] != last) {
				int index = (last == '1' ? 1 : 0);
				ret[index] = std::max(size, ret[index]);
				size = 0;
			}
			last = s[i];
			++size;
		}
		if (size != 0) {
			int index = (last == '1' ? 1 : 0);
			ret[index] = std::max(size, ret[index]);
		}
		return ret[1] > ret[0];
	}

	//面试题 01.06. 字符串压缩
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		90.43 %
		的用户
		内存消耗：
		7.1 MB
		, 在所有 C++ 提交中击败了
		90.81 %
		的用户*/
	string compressString(string S) {
		char last{ '0' };
		int size{};

		string ret;
		for (int i = 0; i < (int)S.size(); i++) {
			if (last != '0' && last != S[i]) {
				ret.push_back(last);
				ret += to_string(size);
				size = 0;
			}
			last = S[i];
			++size;
		}

		if (size != 0) {
			ret.push_back(last);
			ret += to_string(size);
		}

		return ret.length() < S.length() ? ret : S;
	}

	//面试题 02.06. 回文链表
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		79.83 %
		的用户
		内存消耗：
		13.5 MB
		, 在所有 C++ 提交中击败了
		55.77 %
		的用户*/
		/*bool isPalindrome(ListNode* head) {
			string str;
			while (head)
			{
				str.push_back((char)(head->val + '0'));
				head = head->next;
			}
			return ::isPalindrome(str);
		}*/

		//1380. 矩阵中的幸运数
		/*执行用时：
			24 ms
			, 在所有 C++ 提交中击败了
			79.18 %
			的用户
			内存消耗：
			11.3 MB
			, 在所有 C++ 提交中击败了
			22.43 %
			的用户*/
	vector<int> luckyNumbers(vector<vector<int>>& matrix) {
		vector<int> columnMax;
		columnMax.resize((int)matrix[0].size(), 0);

		auto getColumnMax = [&matrix, &columnMax](int col) {
			if (columnMax[col] == 0) {
				for (int i = 0; i < (int)matrix.size(); i++)
					columnMax[col] = std::max(matrix[i][col], columnMax[col]);
			}
			return columnMax[col];
		};

		vector<int> ret;
		for (int i = 0; i < (int)matrix.size(); i++) {
			auto it = min_element(matrix[i].begin(), matrix[i].end());
			int j = (int)distance(matrix[i].begin(), it);
			if (*it == getColumnMax(j))
				ret.emplace_back(*it);
		}
		return ret;
	}

	//1455. 检查单词是否为句中其他单词的前缀
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		56.76 %
		的用户*/
	int isPrefixOfWord(string sentence, string searchWord) {
		auto words = splitString(sentence.c_str());
		for (int i = 0; i < (int)words.size(); i++) {
			size_t pos = words[i].find(searchWord);
			if (pos == 0)
				return i + 1;
		}
		return -1;
	}

	//696. 计数二进制子串
	/*执行用时：
		20 ms
		, 在所有 C++ 提交中击败了
		86.11 %
		的用户
		内存消耗：
		10.2 MB
		, 在所有 C++ 提交中击败了
		75.84 %
		的用户*/
	int countBinarySubstrings(string s) {
		int ptr = 0, n = (int)s.size(), last = 0, ans = 0;
		while (ptr < n) {
			char c = s[ptr];
			int count = 0;
			while (ptr < n && s[ptr] == c) {
				++ptr;
				++count;
			}
			ans += min(count, last);
			last = count;
		}
		return ans;
	}

	//874. 模拟行走机器人
	int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
		enum Direction
		{
			North = 0,
			East = 1,
			South = 2,
			West = 3,
		};

		vector<int> pos{ 0, 0 };
		int dir = Direction::North;

		auto changeDir = [&dir](int command) {
			switch (command) {
			case -2:
				--dir;
				break;
			case -1:
				++dir;
				break;
			default:
				break;
			}

			if (dir == -1)
				dir = West;
			else if (dir == 4)
				dir = North;
		};

		auto isCollision = [&obstacles](const vector<int>& pos) {
			return find(obstacles.begin(), obstacles.end(), pos) != obstacles.end();
		};

		auto doMove = [&pos, &dir, &obstacles, &isCollision](int command) {
			for (int i = 0; i < command; i++) {
				vector<int> temp(pos);
				switch (dir) {
				case North:
					++temp[1];
					break;
				case East:
					++temp[0];
					break;
				case South:
					--temp[1];
					break;
				case West:
					--temp[0];
					break;
				default:
					break;
				}

				if (!isCollision(temp))
					pos = std::move(temp);
				else
					break;
			}
		};

		for (int i = 0; i < (int)commands.size(); i++) {
			switch (commands[i]) {
			case -2:
			case -1:
				changeDir(commands[i]);
				break;
			default:
				doMove(commands[i]);
				break;
			}
		}

		return pos[0] * pos[0] + pos[1] * pos[1];
	}

	//342. 4的幂
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		22.30 %
		的用户*/
	bool isPowerOfFour(int n) {
		if (n <= 0)
			return false;

		while (n > 1) {
			if (n % 4 != 0)
				return false;
			n >>= 2;
		};

		return true;
	}

	//1576. 替换所有的问号
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		20.04 %
		的用户*/
		/*string modifyString(string s) {
			for (int i = 0; i < (int)s.length(); i++)
			{
				if (s[i] == '?')
				{
					char prev = i > 0 ? s[i - 1] : '/0';
					char next = i < (int)s.length() - 1 ? s[i + 1] : '/0';
					char c = 'a';
					while (c == prev || c == next)
						++c;
					s[i] = c;
				}
			}
			return std::move(s);
		}*/

		//477. 汉明距离总和
		/*执行用时：
			40 ms
			, 在所有 C++ 提交中击败了
			95.65 %
			的用户
			内存消耗：
			18.6 MB
			, 在所有 C++ 提交中击败了
			7.61 %
			的用户*/
	int totalHammingDistance(vector<int>& nums) {
		int ans = 0, n = (int)nums.size();
		for (int i = 0; i < 30; ++i) {
			int c = 0;
			for (int val : nums) {
				c += (val >> i) & 1;
			}
			ans += c * (n - c);
		}
		return ans;
	}

	//461. 汉明距离
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		47.70 %
		的用户*/
	int hammingDistance(int x, int y) {
		bitset<32> bs(x ^ y);
		return (int)bs.count();
	}

	//1828. 统计一个圆中点的数目
	/*执行用时：
		104 ms
		, 在所有 C++ 提交中击败了
		72.42 %
		的用户
		内存消耗：
		15.7 MB
		, 在所有 C++ 提交中击败了
		91.26 %
		的用户*/
	vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
		vector<int> ret;
		for (const auto& querie : queries) {
			int count{};
			for (const auto& point : points) {
				if (pointInCircle(point, querie))
					++count;
			}
			ret.emplace_back(count);
		}
		return ret;
	}

	//面试题 16.01. 交换数字
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		7 MB
		, 在所有 C++ 提交中击败了
		75.13 %
		的用户*/
	vector<int> swapNumbers(vector<int>& numbers) {
		swap2(numbers[0], numbers[1]);
		return numbers;
	}

	//1833. 雪糕的最大数量
	/*执行用时：
		168 ms
		, 在所有 C++ 提交中击败了
		84.23 %
		的用户
		内存消耗：
		74.7 MB
		, 在所有 C++ 提交中击败了
		20.70 %
		的用户*/
	int maxIceCream(vector<int>& costs, int coins) {
		sort(costs.begin(), costs.end());

		int i{};
		for (; i < (int)costs.size(); i++) {
			coins -= costs[i];
			if (coins <= 0)
				return coins == 0 ? i + 1 : i;
		}
		return i;
	}

	//剑指 Offer 64. 求1+2+…+n
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		63.71 %
		的用户*/
	int sumNums(int n) {
		if (n == 1)
			return 1;
		return n + sumNums(n - 1);
	}

	//剑指 Offer 57 - II. 和为s的连续正数序列
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		61.75 %
		的用户
		内存消耗：
		6.4 MB
		, 在所有 C++ 提交中击败了
		97.62 %
		的用户*/
	vector<vector<int>> findContinuousSequence(int target) {
		vector<vector<int>> ret;
		for (int i = 1; i <= target * 0.5; i++) {
			int sum{};
			int n{ i };
			while (sum < target)
				sum += n++;

			if (sum == target) {
				vector<int> temp;
				for (int j = i; j < n; j++)
					temp.emplace_back(j);
				ret.emplace_back(temp);
			}
		}
		return ret;
	}

	//338. 比特位计数
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		95.07 %
		的用户
		内存消耗：
		8.3 MB
		, 在所有 C++ 提交中击败了
		15.15 %
		的用户*/
	vector<int> countBits(int n) {
		vector<int> ret;
		for (int i = 0; i <= n; i++) {
			bitset<32> bs(i);
			ret.emplace_back((int)bs.count());
		}
		return ret;
	}

	//1837. K 进制表示下的各位数字总和
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		30.66 %
		的用户*/
	int sumBase(int n, int k) {
		int ret{};
		while (n != 0) {
			ret += (n % k);
			n /= k;
		}
		return ret;
	}

	//1796. 字符串中第二大的数字
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		22.30 %
		的用户
		内存消耗：
		9.1 MB
		, 在所有 C++ 提交中击败了
		5.08 %
		的用户*/
	int secondHighest(string s) {
		std::set<int> temp;
		for (const char& c : s) {
			if (isdigit(c))
				temp.emplace(c - '0');
		}
		return temp.size() > 1 ? *(++temp.rbegin()) : -1;
	}

	//剑指 Offer 53 - II. 0～n-1中缺失的数字
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		84.23 %
		的用户
		内存消耗：
		16.6 MB
		, 在所有 C++ 提交中击败了
		88.02 %
		的用户*/
	int missingNumber2(vector<int>& nums) {
		vector<bool> temp;
		temp.resize(nums.size() + 1, false);
		for (auto n : nums)
			temp[n] = true;
		for (int i = 0; i < (int)temp.size(); i++) {
			if (!temp[i])
				return i;
		}
		return -1;
	}

	//1742. 盒子中小球的最大数量
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		90.09 %
		的用户
		内存消耗：
		5.7 MB
		, 在所有 C++ 提交中击败了
		97.41 %
		的用户*/
	int countBalls(int lowLimit, int highLimit) {
		vector<int> temp;
		temp.resize(50, 0);
		for (int i = lowLimit; i <= highLimit; i++) {
			int index = ::digitSum(i);
			++temp[index];
		}
		return *max_element(temp.begin(), temp.end());
	}

	//1859. 将句子排序
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		31.19 %
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		97.69 %
		的用户*/
	string sortSentence(string s) {
		auto result = splitString(s.c_str());
		sort(result.begin(), result.end(), [](const string& a, const string& b) {
			return *a.rbegin() < *b.rbegin();
			});

		s = "";
		for (const auto& word : result) {
			s += word.substr(0, word.length() - 1) + " ";
		}
		s = s.substr(0, s.length() - 1);
		return s;
	}

	//面试题 16.05. 阶乘尾数
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		47.49 %
		的用户*/
	int trailingZeroes(int n) {
		int res = 0;
		while (n >= 5) {
			res += n / 5;
			n /= 5;
		}
		return res;
	}

	//1346. 检查整数及其两倍数是否存在
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		78.73 %
		的用户
		内存消耗：
		11 MB
		, 在所有 C++ 提交中击败了
		17.11 %
		的用户*/
	bool checkIfExist(vector<int>& arr) {
		unordered_set<int> temp;
		for (int n : arr) {
			if (abs(n) < 2 && temp.find(n) != temp.end())
				return true;
			temp.insert(n);
		}

		temp.erase(0);
		temp.erase(1);
		temp.erase(-1);

		for (int i = 0; i < (int)arr.size(); i++) {
			if ((arr[i] & 1) != 0)
				continue;

			if (temp.find(arr[i] * 2) != temp.end()
				|| temp.find(int(arr[i] * 0.5)) != temp.end())
				return true;
		}
		return false;
	}

	//1854. 人口最多的年份
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		91.76 %
		的用户
		内存消耗：
		8.3 MB
		, 在所有 C++ 提交中击败了
		13.08 %
		的用户*/
	int maximumPopulation(vector<vector<int>>& logs) {
		vector<int> temp;
		temp.resize(2050, 0);

		int maxNum{};
		int ret{ 2050 };

		for (const auto& log : logs) {
			for (int i = log[0]; i < log[1]; ++i) {
				++temp[i];
				if (temp[i] > maxNum || (temp[i] == maxNum && i < ret)) {
					maxNum = temp[i];
					ret = i;
				}
			}
		}

		return ret;
	}

	//206. 反转链表
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		66.74 %
		的用户
		内存消耗：
		7.9 MB
		, 在所有 C++ 提交中击败了
		95.86 %
		的用户*/
		/*ListNode* reverseList(ListNode* head) {
			ListNode* prev{ nullptr };
			while (head) {
				ListNode* next = head->next;

				head->next = prev;
				prev = head;
				head = next;
			}
			return prev;
		}*/

		/*ListNode* reverseList(ListNode* head) {
			if (!head || !head->next) {
				return head;
			}
			ListNode* newHead = reverseList(head->next);
			head->next->next = head;
			head->next = nullptr;
			return newHead;
		}*/

		//1848. 到目标元素的最小距离
		/*执行用时：
			0 ms
			, 在所有 C++ 提交中击败了
			100.00 %
			的用户
			内存消耗：
			9.4 MB
			, 在所有 C++ 提交中击败了
			71.57 %
			的用户*/
	int getMinDistance(vector<int>& nums, int target, int start) {
		int offset{};
		int size = (int)nums.size();
		while (start - offset >= 0 || start + offset < size) {
			int left{ start - offset };
			if (left >= 0 && nums[left] == target)
				return offset;

			int right{ start + offset };
			if (right < size && nums[right] == target)
				return offset;

			++offset;
		}
		return offset;
	}

	//剑指 Offer 03. 数组中重复的数字
	/*执行用时：
		36 ms
		, 在所有 C++ 提交中击败了
		91.86 %
		的用户
		内存消耗：
		22.9 MB
		, 在所有 C++ 提交中击败了
		46.86 %
		的用户*/
	int findRepeatNumber(vector<int>& nums) {
		vector<bool> vector;
		vector.resize(100000, false);
		for (const auto& n : nums) {
			if (vector[n])
				return n;
			else
				vector[n] = true;
		}
		return -1;
	}

	//剑指 Offer 57. 和为s的两个数字
	/*执行用时：
		196 ms
		, 在所有 C++ 提交中击败了
		91.79 %
		的用户
		内存消耗：
		98.1 MB
		, 在所有 C++ 提交中击败了
		93.59 %
		的用户*/
		/*vector<int> twoSum(vector<int>& nums, int target) {
			int first{ 0 };
			int last{ (int)nums.size() - 1 };
			while (first < last)
			{
				int sum = nums[first] + nums[last];
				if (sum < target)
					++first;
				else if (sum > target)
					--last;
				else
					return { nums[first], nums[last] };
			}
			return {};
		}*/

		//1816. 截断句子
		/*执行用时：
			0 ms
			, 在所有 C++ 提交中击败了
			100.00 %
			的用户
			内存消耗：
			6.3 MB
			, 在所有 C++ 提交中击败了
			68.42 %
			的用户*/
	string truncateSentence(string s, int k) {
		int i = 0;
		for (; i < (int)s.length(); ++i) {
			if (s[i] == ' ')
				--k;
			if (k == 0)
				break;
		}
		return s.substr(0, i);
	}

	//1812. 判断国际象棋棋盘中一个格子的颜色
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		63.54 %
		的用户*/
	bool squareIsWhite(string coordinates) {
		int value{};
		value += coordinates[0] - 'a';
		value += coordinates[1] - '1';
		return value % 2 != 0;
	}

	//1827. 最少操作使数组递增
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		99.04 %
		的用户
		内存消耗：
		15.4 MB
		, 在所有 C++ 提交中击败了
		59.63 %
		的用户*/
	int minOperations(vector<int>& nums) {
		if (nums.size() < 2) {
			return 0;
		}

		int ret{};
		for (int i = 0; i < (int)nums.size() - 1; i++) {
			if (nums[i] >= nums[i + 1]) {
				int diff = nums[i] - nums[i + 1] + 1;
				nums[i + 1] += diff;
				ret += diff;
			}
		}
		return ret;
	}

	//1844. 将所有数字用字符替换
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		40.64 %
		的用户*/
	string replaceDigits(string s) {
		for (int i = 1; i < (int)s.length(); i += 2) {
			s[i] = s[i - 1] + (s[i] - '0');
		}
		return s;
	}

	//1832. 判断句子是否为全字母句
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		6.3 MB
		, 在所有 C++ 提交中击败了
		79.89 %
		的用户*/
	bool checkIfPangram(string sentence) {
		std::bitset<26> bs;
		for (auto c : sentence) {
			bs.set(c - 'a', true);
		}
		return bs.all();
	}

	//1822. 数组元素积的符号
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		90.09 %
		的用户
		内存消耗：
		9.9 MB
		, 在所有 C++ 提交中击败了
		39.89 %
		的用户*/
	int arraySign(vector<int>& nums) {
		bool ret{ true };
		for (auto n : nums) {
			if (n == 0)
				return 0;
			else if (n < 0)
				ret = !ret;
		}
		return ret ? 1 : -1;
	}

	//897. 递增顺序搜索树
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		7.7 MB
		, 在所有 C++ 提交中击败了
		50.00 %
		的用户*/
	void traverseBST(TreeNode* root, vector<TreeNode*>& result) {
		if (!root) {
			return;
		}
		traverseBST(root->left, result);
		//cout<<root->val<<endl;
		if (!result.empty()) {
			auto last = *result.rbegin();
			last->left = nullptr;
			last->right = root;
		}
		result.emplace_back(root);
		traverseBST(root->right, result);
	}

	TreeNode* increasingBST(TreeNode* root) {
		vector<TreeNode*> result;
		traverseBST(root, result);
		auto last = *result.rbegin();
		last->left = nullptr;
		last->right = nullptr;
		return *result.begin();
	}

	//27. 移除元素
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00 %
		的用户
		内存消耗：
		8.5 MB
		, 在所有 C++ 提交中击败了
		72.86 %
		的用户*/
	int removeElement(vector<int>& nums, int val) {
		int left = 0, right = (int)nums.size();
		while (left < right) {
			if (nums[left] == val) {
				nums[left] = nums[right - 1];
				right--;
			}
			else {
				left++;
			}
		}
		return left;
	}

	//74. 搜索二维矩阵
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		9.3 MB
		, 在所有 C++ 提交中击败了
		48.16%
		的用户*/
		/*bool searchMatrix(vector<vector<int>>& matrix, int target) {
			for (int i = 0; i < (int)matrix.size(); i++) {
				for (int j = 0; j < (int)matrix[i].size(); j++) {
					if (matrix[i][j] == target) {
						return true;
					}
					else if (matrix[i][j] > target) {
						return false;
					}
				}
			}
			return false;
		}*/

		//190. 颠倒二进制位
		/*执行用时：
			0 ms
			, 在所有 C++ 提交中击败了
			100.00%
			的用户
			内存消耗：
			6 MB
			, 在所有 C++ 提交中击败了
			24.63%
			的用户*/
	uint32_t reverseBits(uint32_t n) {
		string&& str = bitset<32>(n).to_string();
		reverse(str.begin(), str.end());
		return bitset<32>(str).to_ulong();
	}

	//面试题 04.02. 最小高度树
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		96.18%
		的用户
		内存消耗：
		23.7 MB
		, 在所有 C++ 提交中击败了
		82.70%
		的用户*/
	TreeNode* sortedArrayToBST(vector<int>& nums, int first, int last) {
		if (first > last)
			return nullptr;
		int mid = first + (int)((last - first + 1) * 0.5);
		TreeNode* root = new TreeNode(nums[mid]);
		root->left = sortedArrayToBST(nums, first, mid - 1);
		root->right = sortedArrayToBST(nums, mid + 1, last);
		return root;
	}

	TreeNode* sortedArrayToBST(vector<int>& nums) {
		return sortedArrayToBST(nums, 0, (int)nums.size() - 1);
	}

	//1614. 括号的最大嵌套深度
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		80.02%
		的用户*/
	int maxDepth(string s) {
		int stack{};
		int ret{};
		for (const char& c : s) {
			if (c == '(')
				++stack;
			else if (c == ')')
				--stack;
			ret = std::max(stack, ret);
		}
		return ret;
	}

	//191. 位1的个数
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		91.58%
		的用户*/
	int hammingWeight(uint32_t n) {
		std::bitset<32> bs(n);
		return (int)bs.count();
	}

	//1768. 交替合并字符串
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.2 MB
		, 在所有 C++ 提交中击败了
		54.38%
		的用户*/
		/*string mergeAlternately(string word1, string word2) {
			string ret;
			int index{};
			while (index < (int)word1.length() || index < (int)word2.length()) {
				if (index < (int)word1.length()) {
					ret.push_back(word1[index]);
				}
				if (index < (int)word2.length()) {
					ret.push_back(word2[index]);
				}
				++index;
			}
			return ret;
		}*/

		//1773. 统计匹配检索规则的物品数量
		/*执行用时：
			80 ms
			, 在所有 C++ 提交中击败了
			86.82%
			的用户
			内存消耗：
			30.1 MB
			, 在所有 C++ 提交中击败了
			66.63%
			的用户*/
	int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
		int ret{};
		int index{};
		if (ruleKey == "color")
			index = 1;
		else if (ruleKey == "name")
			index = 2;
		for (const auto& item : items) {
			if (item[index] == ruleValue)
				++ret;
		}
		return ret;
	}

	//599. 两个列表的最小索引总和
	/*执行用时：
		232 ms
		, 在所有 C++ 提交中击败了
		7.22%
		的用户
		内存消耗：
		29.4 MB
		, 在所有 C++ 提交中击败了
		96.53%
		的用户*/
	vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
		vector<string> ret;
		int lastSum{ INT_MAX };
		for (int i = 0; i < (int)list1.size(); i++) {
			for (int j = 0; j < (int)list2.size(); j++) {
				int indexSum = i + j;
				if (list1[i] == list2[j] && indexSum <= lastSum) {
					if (indexSum < lastSum)
						ret.clear();
					ret.emplace_back(list1[i]);
					lastSum = indexSum;
				}
			}
		}
		return ret;
	}

	//面试题 16.11. 跳水板
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		88.49%
		的用户
		内存消耗：
		19.6 MB
		, 在所有 C++ 提交中击败了
		71.43%
		的用户*/
	vector<int> divingBoard(int shorter, int longer, int k) {
		vector<int> result;
		if (k <= 0)
			return result;

		result.emplace_back(shorter * k);

		int length = (longer - shorter);
		if (length <= 0)
			return result;

		for (int i = 0; i < k; i++)
			result.emplace_back(*result.rbegin() + length);
		return result;
	}

	//925. 长按键入
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.2 MB
		, 在所有 C++ 提交中击败了
		84.57%
		的用户*/
	bool isLongPressedName(string name, string typed) {
		int i = 0, j = 0;
		for (; i < (int)name.length() && j < (int)typed.length();) {
			char a = name[i]; char b = typed[j];
			if (a != b)
				return false;
			else if (i < (int)name.length() - 1 && a == name[i + 1]) {
				++i; ++j;
			}
			else //最长匹配
			{
				++i;

				do {
					++j;
				} while (j < (int)typed.length() && a == typed[j]);
			}
		}
		return (i == (int)name.length()) && (j == (int)typed.length());
	}

	//剑指 Offer 61. 扑克牌中的顺子
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		9.9 MB
		, 在所有 C++ 提交中击败了
		84.85%
		的用户*/
	bool isStraight(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int zero{};
		for (int i = 0; i < (int)nums.size() - 1; i++) {
			if (nums[i] == 0)
				++zero;
			else {
				if (nums[i] == nums[i + 1])
					return false;

				zero -= (nums[i + 1] - nums[i] - 1);
				if (zero < 0) {
					return false;
				}
			}
		}
		return true;
	}

	//1550. 存在连续三个奇数的数组
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		91.73%
		的用户
		内存消耗：
		8.1 MB
		, 在所有 C++ 提交中击败了
		81.98%
		的用户*/
	bool threeConsecutiveOdds(vector<int>& arr) {
		int count{};
		for (int i = 0; i < (int)arr.size(); i++) {
			if (arr[i] & 1)
				++count;
			else
				count = 0;

			if (count >= 3)
				return true;
		}
		return false;
	}

	//766. 托普利茨矩阵
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		94.22%
		的用户
		内存消耗：
		16.9 MB
		, 在所有 C++ 提交中击败了
		93.84%
		的用户*/
	bool isToeplitzMatrix(vector<vector<int>>& matrix, int m, int n) {
		for (int i = m, j = n; i < (int)matrix.size() && j < (int)matrix[0].size(); i++, j++) {
			if (matrix[i][j] != matrix[m][n])
				return false;
		}
		return true;
	}

	bool isToeplitzMatrix(vector<vector<int>>& matrix) {
		for (int i = 0; i < (int)matrix.size(); i++) {
			if (!isToeplitzMatrix(matrix, i, 0)) {
				return false;
			}
		}

		for (int j = 1; j < (int)matrix[0].size(); j++) {
			if (!isToeplitzMatrix(matrix, 0, j)) {
				return false;
			}
		}

		return true;
	}

	//1337. 矩阵中战斗力最弱的 K 行
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		86.74%
		的用户
		内存消耗：
		10.1 MB
		, 在所有 C++ 提交中击败了
		96.58%
		的用户*/
	vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
		vector<int> result;
		for (int j = 0; j < (int)mat[0].size(); j++) {
			for (int i = 0; i < (int)mat.size(); i++) {
				//cout<<mat[i][j]<<" ";
				if (mat[i][j] == 0 && find_if(result.begin(), result.end(), [&i](int index) {
					return index == i;
					}) == result.end()) {
					result.emplace_back(i);
					if ((int)result.size() == k) {
						return result;
					}
				}
			}
			//cout << endl;
		}
		for (int i = 0; i < (int)mat.size(); i++) {
			if (find_if(result.begin(), result.end(), [&i](int index) {
				return index == i;
				}) == result.end()) {
				result.emplace_back(i);
				if ((int)result.size() == k) {
					return result;
				}
			}
		}
		return result;
	}

	//1732. 找到最高海拔
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		7.8 MB
		, 在所有 C++ 提交中击败了
		35.65%
		的用户*/
	int largestAltitude(vector<int>& gain) {
		int result{};
		int sum{};
		for (int i = 0; i < (int)gain.size(); i++) {
			sum += gain[i];
			result = std::max(sum, result);
		}
		return result;
	}

	//1725. 可以形成最大正方形的矩形数目
	/*执行用时：
		44 ms
		, 在所有 C++ 提交中击败了
		87.37%
		的用户
		内存消耗：
		18 MB
		, 在所有 C++ 提交中击败了
		50.89%
		的用户*/
	int countGoodRectangles(vector<vector<int>>& rectangles) {
		std::map<int, int> result;
		for (const auto& rectangle : rectangles) {
			++result[std::min(rectangle[0], rectangle[1])];
		}
		return (*result.rbegin()).second;
	}

	//剑指 Offer 17. 打印从1到最大的n位数
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		99.03%
		的用户
		内存消耗：
		10.3 MB
		, 在所有 C++ 提交中击败了
		99.45%
		的用户*/
	vector<int> printNumbers(int n) {
		n = stoi(string(n, '9'));
		vector<int> result;
		result.resize(n);
		for (int i = 1; i <= n; i++) {
			result[i - 1] = i;
		}
		return result;
	}

	//1232. 缀点成线
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		92.01%
		的用户
		内存消耗：
		9.8 MB
		, 在所有 C++ 提交中击败了
		68.49%
		的用户*/
	bool checkStraightLine(vector<vector<int>>& coordinates) {
		int deltaX = coordinates[1][0] - coordinates[0][0]; //x1 - x0
		int deltaY = coordinates[1][1] - coordinates[0][1]; //y1 - y0
		return find_if(coordinates.begin() + 2, coordinates.end(), [&](const vector<int>& coordinate) {
			//(x - x0) * (y1 - y0) != (y - y0) * (x1 - x0)
			return (coordinate[0] - coordinates[0][0]) * deltaY != (coordinate[1] - coordinates[0][1]) * deltaX;
			}) == coordinates.end();
	}

	//1716. 计算力扣银行的钱
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		5.8 MB
		, 在所有 C++ 提交中击败了
		92.86%
		的用户*/
	int totalMoney(int n) {
		int result{};
		for (int i = 0; i < n; i++) {
			result += (i % 7 + 1) + (i / 7);
		}
		return result;
	}

	//1436. 旅行终点站
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		97.49%
		的用户
		内存消耗：
		10.9 MB
		, 在所有 C++ 提交中击败了
		69.72%
		的用户*/
	string destCity(vector<vector<string>>& paths) {
		std::unordered_set<string> cityA;
		std::unordered_set<string> cityB;

		for (const auto& path : paths) {
			cityA.insert(path[0]);
			cityB.insert(path[1]);
		}

		for (auto it = cityB.begin(); it != cityB.end();) {
			if (cityA.find(*it) != cityA.end())
				it = cityB.erase(it);
			else
				++it;
		}

		return *cityB.begin();
	}

	//1356. 根据数字二进制下 1 的数目排序
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		99.99%
		的用户
		内存消耗：
		9.7 MB
		, 在所有 C++ 提交中击败了
		99.90%
		的用户*/
	vector<int> sortByBits(vector<int>& arr) {
		sort(arr.begin(), arr.end(), [](int a, int b) {
			int countA = (int)bitset<14>(a).count();
			int countB = (int)bitset<14>(b).count();
			if (countA == countB)
				return a < b;
			else
				return countA < countB;
			});
		return arr;
	}

	//1374. 生成每种字符都是奇数个的字符串
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.4 MB
		, 在所有 C++ 提交中击败了
		75.27%
		的用户*/
	string generateTheString(int n) {
		if (n & 1)
			return string(n, 'a');
		else {
			string s(n - 1, 'a');
			s.push_back('b');
			return s;
		}
	}

	//1704. 判断字符串的两半是否相似
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		82.51%
		的用户
		内存消耗：
		6.4 MB
		, 在所有 C++ 提交中击败了
		99.66%
		的用户*/
	bool halvesAreAlike(string s) {
		auto func = [](char c) -> bool {
			return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
				|| c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
		};

		int length = (int)s.length() >> 1;
		int a = (int)count_if(s.begin(), s.begin() + length, func);
		int b = (int)count_if(s.begin() + length, s.end(), func);
		return a == b;
	}

	//1528. 重新排列字符串
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		96.78%
		的用户
		内存消耗：
		14.8 MB
		, 在所有 C++ 提交中击败了
		96.24%
		的用户*/
	string restoreString(string s, vector<int>& indices) {
		vector<char> result;
		result.resize(s.length());
		for (int i = 0; i < (int)indices.size(); i++) {
			result[indices[i]] = s[i];
		}
		return string{ result.begin(), result.end() };
	}

	//1460. 通过翻转子数组使两个数组相等
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		99.81%
		的用户
		内存消耗：
		13.6 MB
		, 在所有 C++ 提交中击败了
		99.81%
		的用户*/
	bool canBeEqual(vector<int>& target, vector<int>& arr) {
		sort(target.begin(), target.end());
		sort(arr.begin(), arr.end());
		return target == arr;
	}

	//1710. 卡车上的最大单元数
	/*执行用时：
		52 ms
		, 在所有 C++ 提交中击败了
		98.92%
		的用户
		内存消耗：
		15.6 MB
		, 在所有 C++ 提交中击败了
		98.01%
		的用户*/
	int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
		std::sort(boxTypes.begin(), boxTypes.end(), [](vector<int>& boxTypeA, vector<int>& boxTypeB) -> bool {
			return boxTypeA[1] > boxTypeB[1];
			});

		int result{};
		for (const auto& boxType : boxTypes) {
			result += std::min(boxType[0], truckSize) * boxType[1];
			if ((truckSize -= boxType[0]) <= 0)
				break;
		}
		return result;
	}

	//628. 三个数的最大乘积
	/*执行用时：
		52 ms
		, 在所有 C++ 提交中击败了
		92.07%
		的用户
		内存消耗：
		26.9 MB
		, 在所有 C++ 提交中击败了
		83.92%
		的用户*/
	int maximumProduct(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int size = (int)nums.size();
		return std::max(std::max(nums[size - 1] * nums[size - 2] * nums[size - 3],
			nums[0] * nums[1] * nums[2]),
			nums[0] * nums[1] * nums[size - 1]);
	}

	//1688. 比赛中的配对次数
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		5.9 MB
		, 在所有 C++ 提交中击败了
		97.10%
		的用户*/
	int numberOfMatches(int n) {
		int result{};
		while (n > 1) {
			if (n % 2 == 0) {
				n /= 2;
				result += n;
			}
			else {
				n = (n - 1) / 2;
				result += n + 1;
			}
		}
		return result;
	}

	//1450. 在既定时间做作业的学生人数
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		11.1 MB
		, 在所有 C++ 提交中击败了
		63.30%
		的用户*/
		/*int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
			int result{};
			for (int i = 0; i < (int)startTime.size(); i++)
			{
				if (queryTime >= startTime[i] && queryTime <= endTime[i])
					++result;
			}
			return result;
		}*/

		//1678. 设计 Goal 解析器
		/*执行用时：
			0 ms
			, 在所有 C++ 提交中击败了
			100.00%
			的用户
			内存消耗：
			6.2 MB
			, 在所有 C++ 提交中击败了
			98.90%
			的用户*/
	string interpret(string command) {
		string result;
		for (int i = 0; i < (int)command.length();) {
			if (command[i] == 'G') {
				result.push_back('G');
				++i;
			}
			else if (command[i] == '(' && command[i + 1] == ')') {
				result.push_back('o');
				i += 2;
			}
			else {
				result.push_back('a');
				result.push_back('l');
				i += 4;
			}
		}
		return result;
	}

	//1684. 统计一致字符串的数目
	/*执行用时：
		136 ms
		, 在所有 C++ 提交中击败了
		44.81%
		的用户
		内存消耗：
		29.8 MB
		, 在所有 C++ 提交中击败了
		86.51%
		的用户*/
	int countConsistentStrings(string allowed, vector<string>& words) {
		int result{};
		for (const auto& word : words) {
			if (std::find_if(word.begin(), word.end(), [&allowed](char c) {
				return allowed.find(c) == std::string::npos;
				}) == word.end())
				++result;
		}
		return result;
	}

	//1720. 解码异或后的数组
	/*执行用时：
		80 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		25.8 MB
		, 在所有 C++ 提交中击败了
		100.00%
		的用户*/
	vector<int> decode(vector<int>& encoded, int first) {
		vector<int> result{ first };
		for (auto e : encoded)
			result.emplace_back(first ^= e);
		return result;
	}

	//605. 种花问题
	/*执行用时：36 ms, 在所有 C++ 提交中击败了85.15%的用户
	内存消耗：20.3 MB, 在所有 C++ 提交中击败了35.64%的用户*/
	/*bool canPlaceFlowers(vector<int>& flowerbed, int n) {
		int count{ 0 };
		int size = (int)flowerbed.size();
		for (int i = 0; i < size; ++i) {
			if (flowerbed[i] == 0) {
				int left = i == 0 ? 0 : flowerbed[i - 1];
				int right = i == size - 1 ? 0 : flowerbed[i + 1];
				if (left == 0 && right == 0) {
					++count;
					++i;
				}
			} else {
				++i;
			}
		}
		return count >= n;
	}*/

	//1033. 移动石子直到连续
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
	内存消耗：6.6 MB, 在所有 C++ 提交中击败了18.48%的用户*/
	vector<int> numMovesStones(int a, int b, int c) {
		vector<int> pos{ a, b, c };
		sort(pos.begin(), pos.end());

		int left = pos[1] - pos[0] - 1;
		int right = pos[2] - pos[1] - 1;
		int minimum_moves = (left > 0 ? 1 : 0) + (right > 0 ? 1 : 0);
		if (left == 1 || right == 1)
			minimum_moves = 1;
		int maximum_moves = left + right;
		return { minimum_moves, maximum_moves };
	}

	//面试题 08.01. 三步问题
	/*执行用时：4 ms, 在所有 C++ 提交中击败了98.76%的用户
	内存消耗：6.2 MB, 在所有 C++ 提交中击败了65.83%的用户*/
	int waysToStep(int n) {
		if (n == 1)
			return 1;

		if (n == 2)
			return 2;

		if (n == 3)
			return 4;

		uint64_t a = 1; uint64_t b = 2; uint64_t c = 4;

		uint64_t ret{ 0 };
		for (int i = 4; i <= n; ++i) {
			ret = (a + b + c) % 1000000007;
			a = b;
			b = c;
			c = ret;
		}
		return (int)ret;
	}

	/*int waysToStep(int n) {
		if (n == 1)
			return 1;

		if (n == 2)
			return 2;

		if (n == 3)
			return 4;

		return waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3);
	}*/

	//1652. 拆炸弹
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		87.81%
		的用户
		内存消耗：
		8.7 MB
		, 在所有 C++ 提交中击败了
		5.07%
		的用户*/
	vector<int> decrypt(vector<int>& code, int k) {
		int size = (int)code.size();
		vector<int> ret(size);
		code.insert(code.end(), code.begin(), code.end());
		if (k > 0) {
			for (int i = 0; i < size; i++) {
				ret[i] = accumulate(code.begin() + 1 + i, code.begin() + 1 + i + k, 0);
			}
		}
		else if (k < 0) {
			for (int i = size - 1; i >= 0; i--) {
				ret[i] = accumulate(code.rbegin() + size - i, code.rbegin() + size - i - k, 0);
			}
		}
		return ret;
	}

	//1266. 访问所有点的最小时间
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		82.35%
		的用户
		内存消耗：
		9.8 MB
		, 在所有 C++ 提交中击败了
		23.53%
		的用户*/
	int minTimeToVisitAllPoints(vector<vector<int>>& points) {
		int ret{};
		for (int i = 0; i < (int)points.size() - 1; i++) {
			const auto& pointA = points[i];
			const auto& pointB = points[i + 1];
			ret += std::max(std::abs(pointB[0] - pointA[0]), std::abs(pointB[1] - pointA[1]));
		}
		return ret;
	}

	//1108. IP 地址无效化
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.3 MB
		, 在所有 C++ 提交中击败了
		14.88%
		的用户*/
	string defangIPaddr(string address) {
		string str;
		for (const char& c : address) {
			if (c == '.') {
				str.push_back('[');
				str.push_back('.');
				str.push_back(']');
			}
			else
				str.push_back(c);
		}
		return str;
	}

	//1389. 按既定顺序创建目标数组
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		8.7 MB
		, 在所有 C++ 提交中击败了
		7.07%
		的用户*/
	vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
		vector<int> ret;
		int size = (int)nums.size();
		for (int i = 0; i < size; ++i) {
			ret.emplace(ret.begin() + index[i], nums[i]);
		}
		return ret;
	}

	//5613. 最富有客户的资产总量
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		66.09%
		的用户
		内存消耗：
		8 MB
		, 在所有 C++ 提交中击败了
		94.68%
		的用户*/
	int maximumWealth(vector<vector<int>>& accounts) {
		std::set<int> set;
		for (const auto& account : accounts) {
			set.insert(accumulate(account.begin(), account.end(), 0));
		}
		return *set.rbegin();
	}

	//976. 三角形的最大周长
	/*执行用时：
		100 ms
		, 在所有 C++ 提交中击败了
		84.63%
		的用户
		内存消耗：
		20.6 MB
		, 在所有 C++ 提交中击败了
		10.99%
		的用户*/
	int largestPerimeter(vector<int>& A) {
		std::sort(A.begin(), A.end(), std::greater<int>());
		for (int i = 0; i < (int)A.size() - 2; i++) {
			int a = A[i];
			int b = A[i + 1];
			int c = A[i + 2];

			if (a < b + c) {
				return a + b + c;
			}
		}
		return 0;
	}

	//1370. 上升下降字符串
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		93.95%
		的用户
		内存消耗：
		7.8 MB
		, 在所有 C++ 提交中击败了
		69.86%
		的用户*/
	string sortString(string s) {
		int arr[26] = { 0 };
		for (const auto& c : s) {
			++arr[c - 'a'];
		}

		string ret;
		while (ret.length() < s.length()) {
			for (int i = 0; i < 26; i++) {
				if (arr[i] == 0)
					continue;
				ret.push_back((char)(i + 'a'));
				--arr[i];
			}

			for (int i = 25; i >= 0; i--) {
				if (arr[i] == 0)
					continue;
				ret.push_back((char)(i + 'a'));
				--arr[i];
			}
		}
		return ret;
	}

	//剑指 Offer 54. 二叉搜索树的第k大节点
	/*执行用时：
		24 ms
		, 在所有 C++ 提交中击败了
		94.89%
		的用户
		内存消耗：
		24.2 MB
		, 在所有 C++ 提交中击败了
		15.41%
		的用户*/
	void kthLargest(TreeNode* root, int k, std::vector<int>& q) {
		if (!root || (int)q.size() >= k) return;
		kthLargest(root->right, k, q);
		if ((int)q.size() < k)
			q.emplace_back(root->val);
		else
			return;
		kthLargest(root->left, k, q);
	}

	int kthLargest(TreeNode* root, int k) {
		std::vector<int> q;
		kthLargest(root, k, q);
		return *q.rbegin();
	}

	//面试题 17.04. 消失的数字
	/*执行用时：
		32 ms
		, 在所有 C++ 提交中击败了
		96.88%
		的用户
		内存消耗：
		17.3 MB
		, 在所有 C++ 提交中击败了
		10.53%
		的用户*/
	int missingNumber(vector<int>& nums) {
		int size = (int)nums.size();
		return int(size * (size + 1) * 0.5) - accumulate(nums.begin(), nums.end(), 0);
	}

	//226. 翻转二叉树
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		9.3 MB
		, 在所有 C++ 提交中击败了
		35.65%
		的用户*/
	TreeNode* invertTree(TreeNode* root) {
		if (root == nullptr) {
			return nullptr;
		}
		TreeNode* left = invertTree(root->left);
		TreeNode* right = invertTree(root->right);
		root->left = right;
		root->right = left;
		return root;
	}

	//1122. 数组的相对排序
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		90.26%
		的用户
		内存消耗：
		8.1 MB
		, 在所有 C++ 提交中击败了
		21.61%
		的用户*/
		/*vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
			vector<int> temp(1001);
			int size = (int)arr2.size();
			for (int i = 0; i < size; i++)
			{
				temp[arr2[i]] = size - i;
			}
			std::sort(arr1.begin(), arr1.end(), [&temp](int a, int b) {
				if (temp[a] == temp[b])
				{
					return a < b;
				}
				return temp[a] > temp[b];
			});
			return arr1;
		}*/

		//832. 翻转图像
		/*执行用时：
			4 ms
			, 在所有 C++ 提交中击败了
			97.72%
			的用户
			内存消耗：
			8.6 MB
			, 在所有 C++ 提交中击败了
			54.41%
			的用户*/
	vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
		for (int i = 0; i < (int)A.size(); ++i) {
			vector<int>& temp = A[i];
			reverse(temp.begin(), temp.end());
			for (int j = 0; j < (int)temp.size(); ++j) {
				temp[j] = !temp[j];
			}
		}
		return A;
	}

	//938. 二叉搜索树的范围和
	/*执行用时：
		208 ms
		, 在所有 C++ 提交中击败了
		90.06%
		的用户
		内存消耗：
		63.7 MB
		, 在所有 C++ 提交中击败了
		36.20%
		的用户*/
	void search(TreeNode* root, int low, int high, int& sum) {
		if (!root)
			return;
		if (root->val > low) {
			search(root->left, low, high, sum);
		}
		if (root->val >= low && root->val <= high) {
			sum += root->val;
		}
		if (root->val < high) {
			search(root->right, low, high, sum);
		}
	}

	int rangeSumBST(TreeNode* root, int low, int high) {
		int sum{ 0 };
		search(root, low, high, sum);
		return sum;
	}

	//922. 按奇偶排序数组 II
	/*执行用时：
		32 ms
		, 在所有 C++ 提交中击败了
		99.05%
		的用户
		内存消耗：
		20.5 MB
		, 在所有 C++ 提交中击败了
		29.90%
		的用户*/
	vector<int> sortArrayByParityII(vector<int>& A) {
		int i = 0; int j = 1;
		while (i < (int)A.size() && j < (int)A.size()) {
			if ((A[i] & 1) == 0)
				i += 2;
			else if ((A[j] & 1) == 1)
				j += 2;
			else
				swap(A[i], A[j]);
		}
		return A;
	}

	//804. 唯一摩尔斯密码词
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		9 MB
		, 在所有 C++ 提交中击败了
		13.23%
		的用户*/
	int uniqueMorseRepresentations(vector<string>& words) {
		static const char* const password[] =
		{
			".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--..",
		};

		auto func = [](const string& str) -> string {
			string ret = "";
			for (const auto& c : str) {
				ret += password[c - 'a'];
			}
			return ret;
		};

		set<string> set;
		for (const auto& s : words) {
			set.emplace(func(s));
		}
		return (int)set.size();
	}

	//剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
	/*执行用时：
		36 ms
		, 在所有 C++ 提交中击败了
		92.57%
		的用户
		内存消耗：
		18.1 MB
		, 在所有 C++ 提交中击败了
		25.92%
		的用户*/
	vector<int> exchange(vector<int>& nums) {
		/*sort(nums.begin(), nums.end(), [](int a, int b) {
			return (a & 1) > (b & 1);
		});
		return nums;*/

		int i = 0; int j = (int)nums.size() - 1;
		while (i < j) {
			if ((nums[i] & 1) == 1)
				++i;
			else if ((nums[j] & 1) == 0)
				--j;
			else
				swap(nums[i], nums[j]);
		}
		return nums;
	}

	//1491. 去掉最低工资和最高工资后的工资平均值
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		7.3 MB
		, 在所有 C++ 提交中击败了
		39.40%
		的用户*/
	double average(vector<int>& salary) {
		sort(salary.begin(), salary.end());
		double sum = accumulate(salary.begin() + 1, salary.end() - 1, 0);
		return sum / (salary.size() - 2);
	}

	//LCP 17. 速算机器人
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.2 MB
		, 在所有 C++ 提交中击败了
		10.74%
		的用户*/
	int calculate(string s) {
		int x{ 1 }; int y{ 0 };
		for (const auto& c : s) {
			if (c == 'A')
				x = 2 * x + y;
			else if (c == 'B')
				y = 2 * y + x;
		}
		return x + y;
	}

	//LCP 01. 猜数字
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.7 MB
		, 在所有 C++ 提交中击败了
		5.41%
		的用户*/
	int game(vector<int>& guess, vector<int>& answer) {
		int result{};
		for (int i = 0; i < 3; ++i) {
			result += (guess[i] == answer[i] ? 1 : 0);
		}
		return result;
	}

	//1572. 矩阵对角线元素的和
	/*执行用时：
		24 ms
		, 在所有 C++ 提交中击败了
		99.85%
		的用户
		内存消耗：
		11.6 MB
		, 在所有 C++ 提交中击败了
		5.25%
		的用户*/
	int diagonalSum(vector<vector<int>>& mat) {
		int sum{ 0 };
		for (int i = 0; i < (int)mat.size(); i++) {
			int size = (int)mat[i].size();
			for (int j = 0; j < size; j++) {
				if (i == j || i == size - 1 - j)
					sum += mat[i][j];
			}
		}
		return sum;
	}

	//面试题 01.01. 判定字符是否唯一
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.2 MB
		, 在所有 C++ 提交中击败了
		42.31%
		的用户*/
	bool isUnique(string astr) {
		std::sort(astr.begin(), astr.end());
		return std::unique(astr.begin(), astr.end()) == astr.end();
	}

	//1512. 好数对的数目
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		7.5 MB
		, 在所有 C++ 提交中击败了
		32.68%
		的用户*/
	int numIdenticalPairs(vector<int>& nums) {
		std::map<int, int> temp;
		for (auto e : nums) {
			++temp[e];
		}

		int result{ 0 };
		for (auto p : temp) {
			if (p.second >= 2) {
				result += p.second * (p.second - 1) / 2;
			}
		}
		return result;
	}

	//121. 买卖股票的最佳时机
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		94.76%
		的用户
		内存消耗：
		13 MB
		, 在所有 C++ 提交中击败了
		18.14%
		的用户*/
	int maxProfit(vector<int>& prices) {
		if (prices.empty())
			return 0;

		int result{ 0 };
		int minPrice{ prices[0] };
		for (int i = 1; i < (int)prices.size(); i++) {
			result = std::max(prices[i] - minPrice, result);
			minPrice = std::min(prices[i], minPrice);
		}
		return result;
	}

	//1431. 拥有最多糖果的孩子
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		84.61%
		的用户
		内存消耗：
		9.3 MB
		, 在所有 C++ 提交中击败了
		6.24%
		的用户*/
	vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
		int maxCandies = *std::max_element(candies.begin(), candies.end());

		vector<bool> result;
		for (const auto& e : candies) {
			result.emplace_back(e + extraCandies >= maxCandies);
		}
		return result;
	}

	//643. 子数组最大平均数 I
	/*执行用时：
		256 ms
		, 在所有 C++ 提交中击败了
		88.19%
		的用户
		内存消耗：
		70.4 MB
		, 在所有 C++ 提交中击败了
		15.61%
		的用户*/
	double findMaxAverage(vector<int>& nums, int k) {
		double sum = accumulate(nums.begin(), nums.begin() + k, 0);
		double result = sum;
		for (int i = 1; i <= (int)nums.size() - k; i++) {
			sum = sum - nums[i - 1] + nums[i - 1 + k];
			result = std::max(sum, result);
		}
		return result / k;
	}

	//1486. 数组异或操作
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.3 MB
		, 在所有 C++ 提交中击败了
		17.35%
		的用户*/
	int xorOperation(int n, int start) {
		int result{ start };
		for (int i = 1; i < n; i++) {
			result ^= (start + 2 * i);
		}
		return result;
	}

	//剑指 Offer 10- II. 青蛙跳台阶问题
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.3 MB
		, 在所有 C++ 提交中击败了
		15.72%
		的用户*/
	int numWays(int n) {
		int a{ 0 };
		int b{ 1 };

		int sum{ 1 };
		for (int i = 1; i <= n; i++) {
			sum = (a + b);
			sum = sum > 1000000007 ? sum % 1000000007 : sum;
			a = b;
			b = sum;
		}
		return sum;
	}

	//70. 爬楼梯
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.3 MB
		, 在所有 C++ 提交中击败了
		21.95%
		的用户*/
	int climbStairs(int n) {
		int a{ 0 };
		int b{ 1 };

		int sum{ 0 };
		for (int i = 1; i <= n; i++) {
			sum = (a + b);
			a = b;
			b = sum;
		}
		return sum;
	}

	//941. 有效的山脉数组
	/*执行用时：
		52 ms
		, 在所有 C++ 提交中击败了
		90.83%
		的用户
		内存消耗：
		22.2 MB
		, 在所有 C++ 提交中击败了
		5.15%
		的用户*/
	bool validMountainArray(vector<int>& A) {
		if (A.size() < 3)
			return false;

		if (A[0] >= A[1])
			return false;

		bool rise{ true };
		for (int i = 1; i < (int)A.size() - 1; ++i) {
			if (A[i] == A[i + 1])
				return false;
			else if (A[i] > A[i + 1])
				rise = false;
			else {
				if (!rise)
					return false;
			}
		}

		return !rise;
	}

	//219. 存在重复元素 II
	/*执行用时：
		72 ms
		, 在所有 C++ 提交中击败了
		34.73%
		的用户
		内存消耗：
		15.6 MB
		, 在所有 C++ 提交中击败了
		90.79%
		的用户*/
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		unordered_set<int> temp;
		for (int i = 0; i < (int)nums.size(); i++) {
			if (temp.find(nums[i]) != temp.end()) return true;
			temp.emplace(nums[i]);
			if ((int)temp.size() > k) {
				temp.erase(nums[i - k]);
			}
		}
		return false;
	}

	//217. 存在重复元素
	/*执行用时：
		56 ms
		, 在所有 C++ 提交中击败了
		97.26%
		的用户
		内存消耗：
		14.8 MB
		, 在所有 C++ 提交中击败了
		91.53%
		的用户*/
	bool containsDuplicate(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		return std::unique(nums.begin(), nums.end()) != nums.end();
	}

	//1475. 商品折扣后的最终价格
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		98.24%
		的用户
		内存消耗：
		10 MB
		, 在所有 C++ 提交中击败了
		45.91%
		的用户*/
	vector<int> finalPrices(vector<int>& prices) {
		for (int i = 0; i < (int)prices.size(); i++) {
			for (int j = i + 1; j < (int)prices.size(); j++) {
				if (prices[j] <= prices[i]) {
					prices[i] -= prices[j];
					break;
				}
			}
		}
		return prices;
	}

	//1342. 将数字变成 0 的操作次数
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6.3 MB
		, 在所有 C++ 提交中击败了
		8.92%
		的用户*/
	int numberOfSteps(int num) {
		bitset<32> bs(num);

		int count{ 0 };
		while (bs.count()) {
			if (bs.test(0))
				bs.reset(0);
			else
				bs >>= 1;
			++count;
		}
		return count;
	}

	//面试题 02.03. 删除中间节点
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		95.32%
		的用户
		内存消耗：
		8.2 MB
		, 在所有 C++ 提交中击败了
		5.53%
		的用户*/
		/*void deleteNode(ListNode* node) {
			node->val = node->next->val;
			node->next = node->next->next;
		}*/

		//5539. 按照频率将数组升序排序
		/*执行用时：
			36 ms
			, 在所有 C++ 提交中击败了
			15.56%
			的用户
			内存消耗：
			11.2 MB
			, 在所有 C++ 提交中击败了
			90.58%
			的用户*/
	vector<int> frequencySort(vector<int>& nums) {
		map<int, int> temp;
		for (auto e : nums) {
			++temp[e];
		}

		sort(nums.begin(), nums.end(), [&temp](int a, int b) {
			if (temp[a] == temp[b]) {
				return a > b;
			}
			return temp[a] < temp[b];
			});
		return nums;
	}

	//1480. 一维数组的动态和
	/*执行用时：
		4 ms
		, 在所有 C++ 提交中击败了
		89.33%
		的用户
		内存消耗：
		8.7 MB
		, 在所有 C++ 提交中击败了
		12.23%
		的用户*/
	vector<int> runningSum(vector<int>& nums) {
		for (int i = 1; i < (int)nums.size(); i++) {
			nums[i] += nums[i - 1];
		}
		return nums;
	}

	//1394. 找出数组中的幸运数
	/*执行用时：
		12 ms
		, 在所有 C++ 提交中击败了
		88.72%
		的用户
		内存消耗：
		10.3 MB
		, 在所有 C++ 提交中击败了
		63.12%
		的用户*/
	int findLucky(vector<int>& arr) {
		map<int, int> temp;
		for (auto e : arr) {
			++temp[e];
		}

		for (auto it = temp.rbegin(); it != temp.rend(); ++it) {
			if (it->first == it->second) {
				return it->first;
			}
		}
		return -1;
	}

	//349. 两个数组的交集
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		96.25%
		的用户
		内存消耗：
		10.3 MB
		, 在所有 C++ 提交中击败了
		79.93%
		的用户*/
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		std::sort(nums1.begin(), nums1.end());
		std::sort(nums2.begin(), nums2.end());

		std::vector<int> v_intersection;
		std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), std::back_inserter(v_intersection));

		auto last = std::unique(v_intersection.begin(), v_intersection.end());
		v_intersection.erase(last, v_intersection.end());

		return v_intersection;
	}

	//1619. 删除某些元素后的数组均值
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		92.65%
		的用户
		内存消耗：
		9.5 MB
		, 在所有 C++ 提交中击败了
		75.66%
		的用户*/
	double trimMean(vector<int>& arr) {
		sort(arr.begin(), arr.end());
		int size = (int)arr.size();
		int num = (int)(size * 0.05);
		double sum = accumulate(arr.begin() + num, arr.end() - num, 0);
		return sum / (size - 2 * num);
	}

	//剑指 Offer 25. 合并两个排序的链表
	/*执行用时：
		32 ms
		, 在所有 C++ 提交中击败了
		98.48%
		的用户
		内存消耗：
		19.2 MB
		, 在所有 C++ 提交中击败了
		41.90%
		的用户*/
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode* head{ new ListNode() };
		ListNode* node{ head };
		while (l1 && l2) {
			if (l1->val < l2->val) {
				node->next = l1;
				l1 = l1->next;
			}
			else {
				node->next = l2;
				l2 = l2->next;
			}
			node = node->next;
		}
		node->next = l1 ? l1 : l2;
		return head->next;
	}

	//21. 合并两个有序链表
	/*ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		if (l1 == nullptr) {
			return l2;
		}
		else if (l2 == nullptr) {
			return l1;
		}
		else if (l1->val < l2->val) {
			l1->next = mergeTwoLists(l1->next, l2);
			return l1;
		}
		else {
			l2->next = mergeTwoLists(l1, l2->next);
			return l2;
		}
	}*/

	//1502. 判断能否形成等差数列
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		85.00%
		的用户
		内存消耗：
		9.1 MB
		, 在所有 C++ 提交中击败了
		34.72%
		的用户*/
	bool canMakeArithmeticProgression(vector<int>& arr) {
		if (arr.size() < 3) {
			return true;
		}

		sort(arr.begin(), arr.end());

		int diff = arr[1] - arr[0];
		for (int i = 1; i < (int)arr.size() - 1; i++) {
			if (arr[i + 1] - arr[i] != diff)
				return false;
		}
		return true;
	}

	//1464. 数组中两元素的最大乘积
	/*执行用时：
		8 ms
		, 在所有 C++ 提交中击败了
		94.42%
		的用户
		内存消耗：
		10 MB
		, 在所有 C++ 提交中击败了
		50.88%
		的用户*/
	int maxProduct(vector<int>& nums) {
		nth_element(nums.begin(), nums.begin() + 2, nums.end(), std::greater<int>());
		return (nums[0] - 1) * (nums[1] - 1);
	}

	//LCP 06. 拿硬币
	/*执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
	内存消耗：8.4 MB, 在所有 C++ 提交中击败了12.28%的用户*/
	/*int minCount(vector<int>& coins) {
		int count{ 0 };
		for (auto coin : coins) {
			count += (coin >> 1) + (coin & 1);
		}
		return count;
	}*/

	//面试题 01.02. 判定是否互为字符重排
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		6 MB
		, 在所有 C++ 提交中击败了
		76.20%
		的用户*/
	bool CheckPermutation(string s1, string s2) {
		std::sort(s1.begin(), s1.end());
		std::sort(s2.begin(), s2.end());
		return s1 == s2;
	}

	//面试题 08.03. 魔术索引
	/*执行用时：
		16 ms
		, 在所有 C++ 提交中击败了
		89.19%
		的用户
		内存消耗：
		12.5 MB
		, 在所有 C++ 提交中击败了
		71.03%
		的用户*/
	int findMagicIndex(vector<int>& nums) {
		for (int i = 0; i < (int)nums.size();) {
			if (nums[i] == i)
				return i;
			else if (nums[i] > i)
				i += (nums[i] - i);
			else
				i++;
		}
		return -1;
	}

	//1748. 唯一元素的和
	/*执行用时：
		0 ms
		, 在所有 C++ 提交中击败了
		100.00%
		的用户
		内存消耗：
		7.9 MB
		, 在所有 C++ 提交中击败了
		5.19%
		的用户*/
	int sumOfUnique(vector<int>& nums) {
		std::map<int, int> map;
		for (auto n : nums) {
			++map[n];
		}

		int sum{};
		for (auto p : map) {
			if (p.second == 1)
				sum += p.first;
		}
		return sum;
	}
};

//1114. 按序打印
//执行用时：128 ms, 在所有 C++ 提交中击败了84.99%的用户
//内存消耗：7.7 MB, 在所有 C++ 提交中击败了14.63%的用户
class Foo
{
public:
	Foo() {
	}

	void first(function<void()> printFirst) {
		// printFirst() outputs "first". Do not change or remove this line.
		printFirst();
		++m_flag;
		m_cv.notify_all();
	}

	void second(function<void()> printSecond) {
		std::unique_lock<std::mutex> lk(m_mutex);
		m_cv.wait(lk, [this] {return m_flag == 1; });
		// printSecond() outputs "second". Do not change or remove this line.
		printSecond();
		++m_flag;
		m_cv.notify_one();
	}

	void third(function<void()> printThird) {
		std::unique_lock<std::mutex> lk(m_mutex);
		m_cv.wait(lk, [this] {return m_flag == 2; });
		// printThird() outputs "third". Do not change or remove this line.
		printThird();
	}

private:
	std::mutex m_mutex;
	std::condition_variable m_cv;
	int m_flag{ 0 };
};

//1603. 设计停车系统
//执行用时：116 ms, 在所有 C++ 提交中击败了82.20%的用户
//内存消耗：32.7 MB, 在所有 C++ 提交中击败了36.14%的用户
class ParkingSystem
{
public:
	ParkingSystem(int big, int medium, int small) {
		m_data[0] = big;
		m_data[1] = medium;
		m_data[2] = small;
	}

	bool addCar(int carType) {
		return m_data[carType - 1]-- > 0;
	}

private:
	vector<int> m_data{ 0, 0, 0 };
};

// This is the interface that allows for creating nested lists.
// You should not implement it, or speculate about its implementation
class NestedInteger
{
public:
	// Return true if this NestedInteger holds a single integer, rather than a nested list.
	bool isInteger() const {
	};

	// Return the single integer that this NestedInteger holds, if it holds a single integer
	// The result is undefined if this NestedInteger holds a nested list
	int getInteger() const {
	};

	// Return the nested list that this NestedInteger holds, if it holds a nested list
	// The result is undefined if this NestedInteger holds a single integer
	const vector<NestedInteger>& getList() const {
	};
};

//341. 扁平化嵌套列表迭代器
//执行用时：
//8 ms
//, 在所有 C++ 提交中击败了
//90.84%
//的用户
//内存消耗：
//13.1 MB
//, 在所有 C++ 提交中击败了
//60.70%
//的用户
class NestedIterator
{
public:
	NestedIterator(vector<NestedInteger>& nestedList) {
		for (const auto& n : nestedList)
			visit(n);
	}

	int next() {
		return m_data[m_index++];
	}

	bool hasNext() {
		return m_index < (int)m_data.size();
	}

private:
	void visit(const NestedInteger& n) {
		if (n.isInteger())
			m_data.emplace_back(n.getInteger());
		else {
			for (const auto& list : n.getList())
				visit(list);
		}
	}

	std::vector<int> m_data;
	int m_index{ 0 };
};

//1656. 设计有序流
//执行用时：
//112 ms
//, 在所有 C++ 提交中击败了
//96.72 %
//的用户
//内存消耗：
//81.6 MB
//, 在所有 C++ 提交中击败了
//82.83 %
//的用户
class OrderedStream
{
public:
	OrderedStream(int n) {
		m_data.resize(n, "");
	}

	vector<string> insert(int idKey, string value) {
		m_data[idKey - 1] = value;

		vector<string> ret;
		for (; m_ptr < (int)m_data.size(); m_ptr++) {
			if (m_data[m_ptr] == "")
				break;
			ret.emplace_back(m_data[m_ptr]);
		}
		return ret;
	}

private:
	vector<string> m_data;
	int m_ptr{};
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */

 //剑指 Offer 09. 用两个栈实现队列
 //执行用时：
 //316 ms
 //, 在所有 C++ 提交中击败了
 //88.60%
 //的用户
 //内存消耗：
 //101.1 MB
 //, 在所有 C++ 提交中击败了
 //64.77%
 //的用户
class CQueue
{
public:
	CQueue() {
		//
	}

	void appendTail(int value) {
		m_stack1.push(value);
	}

	int deleteHead() {
		if (m_stack2.empty()) {
			while (!m_stack1.empty()) {
				m_stack2.push(m_stack1.top());
				m_stack1.pop();
			}
		}

		int value{ -1 };
		if (!m_stack2.empty()) {
			value = m_stack2.top();
			m_stack2.pop();
		}
		return value;
	}

private:
	std::stack<int> m_stack1;
	std::stack<int> m_stack2;
};

//面试题 03.02. 栈的最小值
//执行用时：
//8 ms
//, 在所有 C++ 提交中击败了
//99.83 %
//的用户
//内存消耗：
//14.7 MB
//, 在所有 C++ 提交中击败了
//81.99 %
//的用户
class MinStack
{
public:
	/** initialize your data structure here. */
	MinStack() {
	}

	void push(int x) {
		m_stack1.push(x);

		if (m_stack2.empty() || m_stack2.top() >= x)
			m_stack2.push(x);
	}

	void pop() {
		if (!m_stack2.empty() && m_stack2.top() == top())
			m_stack2.pop();

		m_stack1.pop();
	}

	int top() {
		return m_stack1.top();
	}

	int getMin() {
		return m_stack2.top();
	}

private:
	std::stack<int> m_stack1;
	std::stack<int> m_stack2;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

 //面试题 03.01. 三合一
 //执行用时：
 //72 ms
 //, 在所有 C++ 提交中击败了
 //88.51 %
 //的用户
 //内存消耗：
 //32.2 MB
 //, 在所有 C++ 提交中击败了
 //54.39 %
 //的用户
class TripleInOne
{
public:
	TripleInOne(int stackSize) {
		m_data.resize(stackSize * 3, 0);
		m_stackSize = stackSize;
	}

	void push(int stackNum, int value) {
		if (m_ptr[stackNum] == m_stackSize)
			return;
		m_data[stackNum * m_stackSize + m_ptr[stackNum]] = value;
		++m_ptr[stackNum];
	}

	int pop(int stackNum) {
		if (isEmpty(stackNum))
			return -1;
		int value = m_data[stackNum * m_stackSize + m_ptr[stackNum] - 1];
		--m_ptr[stackNum];
		return value;
	}

	int peek(int stackNum) {
		if (isEmpty(stackNum))
			return -1;
		return m_data[stackNum * m_stackSize + m_ptr[stackNum] - 1];
	}

	bool isEmpty(int stackNum) {
		return m_ptr[stackNum] == 0;
	}

private:
	vector<int> m_data;
	vector<int> m_ptr{ 0, 0, 0 };
	int m_stackSize{};
};

/**
 * Your TripleInOne object will be instantiated and called as such:
 * TripleInOne* obj = new TripleInOne(stackSize);
 * obj->push(stackNum,value);
 * int param_2 = obj->pop(stackNum);
 * int param_3 = obj->peek(stackNum);
 * bool param_4 = obj->isEmpty(stackNum);
 */

 //剑指 Offer II 059. 数据流的第 K 大数值
 //执行用时：
 //28 ms
 //, 在所有 C++ 提交中击败了
 //89.49 %
 //的用户
 //内存消耗：
 //19.4 MB
 //, 在所有 C++ 提交中击败了
 //44.23 %
 //的用户
class KthLargest
{
public:
	priority_queue<int, vector<int>, greater<int>> q;
	int k;
	KthLargest(int k, vector<int>& nums) {
		this->k = k;
		for (auto& x : nums) {
			add(x);
		}
	}

	int add(int val) {
		q.push(val);
		if ((int)q.size() > k) {
			q.pop();
		}
		return q.top();
	}
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

 //731. 我的日程安排表 II
//执行用时：
//100 ms
//, 在所有 C++ 提交中击败了
//92.57 %
//的用户
//内存消耗：
//32.8 MB
//, 在所有 C++ 提交中击败了
//99.80 %
//的用户
class MyCalendarTwo
{
public:
	MyCalendarTwo() {
	}

	bool book(int start, int end) {
		for (auto& [l, r] : overlaps) {
			if (isOverlap(start, end, l, r))
				return false;
		}

		for (auto& [l, r] : booked) {
			if (isOverlap(start, end, l, r))
				overlaps.emplace_back(max(l, start), min(r, end));
		}

		booked.emplace_back(start, end);

		return true;
	}
private:
	bool isOverlap(int start, int end, int l, int r) {
		return !(start >= r || l >= end);
	}

	vector<pair<int, int>> booked;
	vector<pair<int, int>> overlaps;
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */

 //449. 序列化和反序列化二叉搜索树
class Codec
{
public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (!root)
			return "null";
		return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		stringstream ss(data);
		return deserializeHelper(ss);
	}

private:
	TreeNode* deserializeHelper(stringstream& ss) {
		string val;
		getline(ss, val, ',');

		if (val == "null")
			return nullptr;

		TreeNode* node = new TreeNode(stoi(val));
		node->left = deserializeHelper(ss);
		node->right = deserializeHelper(ss);
		return node;
	}
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;

class Logger {
public:
	Logger() {
	}

	bool shouldPrintMessage(int timestamp, string message) {
		auto it = mHashTable.find(message);
		if (it == mHashTable.end())
			mHashTable.insert({ message, timestamp });
		else
		{
			if (timestamp - it->second < 10)
				return false;
			it->second = timestamp;
		}
		return true;
	}

private:
	unordered_map<string, int> mHashTable;
};

/**
 * Your Logger object will be instantiated and called as such:
 * Logger* obj = new Logger();
 * bool param_1 = obj->shouldPrintMessage(timestamp,message);
 */

class TwoSum {
public:
	TwoSum() {
	}

	void add(int number) {
		++mHashTable[number];
	}

	bool find(int value) {
		for (const auto& p : mHashTable) {
			int a = p.first;
			long long b = (long long)value - a;
			if (b > INT_MAX || b < INT_MIN)
				continue;
			auto it = mHashTable.find(b);
			if (it != mHashTable.end()) {
				if (a != b || it->second >= 2)
					return true;
			}
		}
		return false;
	}

private:
	unordered_map<int, int> mHashTable;
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */

class TimeMap {
public:
	TimeMap() {
	}

	void set(string key, string value, int timestamp) {
		mHashTable[key].emplace_back(make_pair(timestamp, value));
	}

	string get(string key, int timestamp) {
		const auto& tmp = mHashTable[key];
		if (tmp.empty() || tmp[0].first > timestamp)
			return "";
		auto it = std::upper_bound(tmp.begin(), tmp.end(), make_pair(timestamp, 0),
			[](auto a, auto b) { return a.first < b.first; });
		return it != tmp.end() ? tmp[std::distance(tmp.begin(), it) - 1].second : tmp.rbegin()->second;
	}

private:
	std::unordered_map<string, vector<pair<int, string>>> mHashTable;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */

class SnapshotArray {
public:
	SnapshotArray(int length) {
		m.emplace_back(unordered_map<int, int>());
	}

	void set(int index, int val) {
		auto&& tmp = *m.rbegin();
		tmp[index] = val;
	}

	int snap() {
		m.emplace_back(unordered_map<int, int>());
		return m.size() - 2;
	}

	int get(int index, int snap_id) {
		for (int i = snap_id; i >= 0; i--) {
			auto&& tmp = m[i];
			auto it = tmp.find(index);
			if (it != tmp.end())
				return it->second;
		}
		return 0;
	}

private:
	vector<unordered_map<int, int>> m;
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

 //class Solution {
 //public:
 //	Solution(vector<int>& w) {
 //		m.emplace_back(w[0]);
 //		for (int i = 1; i < w.size(); i++) {
 //			m.emplace_back(*m.rbegin() + w[i]);
 //		}
 //	}
 //
 //	int pickIndex() {
 //		int random = rand() % *m.rbegin(); //[0, sum)
 //		int left = 0, right = m.size() - 1;
 //		while (left <= right)
 //		{
 //			int mid = left + ((right - left) >> 1);
 //			int prev = mid > 0 ? m[mid - 1] : 0;
 //			if (random >= prev && random < m[mid])
 //				return mid;
 //			else if (random >= m[mid])
 //				left = mid + 1;
 //			else
 //				right = mid - 1;
 //		}
 //		return -1;
 //	}
 //
 //private:
 //	vector<int> m;
 //};

 /**
  * Your Solution object will be instantiated and called as such:
  * Solution* obj = new Solution(w);
  * int param_1 = obj->pickIndex();
  */
